akhauriyash/Code-Regression huggingface dataset:
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    db n,a;
    cin>>n;
    a=n/3.0;
    cout<<fix<<a*a*a;
    return 0;
}


Measured memory_bytes: 256
r1, c1, r2, c2 = map(int, input().split())
L = 10 ** 9 + 7

# 互除法
def get_euclidian (A, B):
  if B == 1:
    return (1)
  else:
    return (int((1 - A * get_euclidian (B, A % B)) / B))

# 階乗計算
F = [1]
for i in range(1, r2 + c2 + 3):
  F.append((F[i - 1] * i) % L)

# 組み合わせ計算
def get_combi (n, r):

  Euc = get_euclidian(L, (F[r] * F[n - r]) % L)
  return ((F[n] * Euc) % L)

combi1 = get_combi(r2 + c2 + 2, r2 + 1)
combi2 = get_combi(r2 + c1 + 1, c1)
combi3 = get_combi(r1 + c2 + 1, r1)
combi4 = get_combi(r1 + c1, r1)

print ((int(combi1 - combi2 - combi3 + combi4) + L) % L)

Measured memory_bytes: 82220
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

n = int(input())
d = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += d[i] * d[j]
print(ans)


Measured memory_bytes: 39024
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll G = 2000005;
ll a,k,mod = 1e9+7;
ll fac[G], inv_fac[G];

ll binpow(ll x, ll K){
    x%=mod;
    if(K<2) return K ? x : 1;
    return (binpow(x*x, K/2)*(K&1 ? x : 1))%mod;
}

ll modinv(ll c){
    return binpow(c, mod-2);
}

ll CizNpoK(ll N, ll K){
    ll o = fac[N]*inv_fac[K];
    o %= mod;
    return (o*inv_fac[N-K])%mod;
}

int main() {
    fast;
    fac[0] = 1;
    inv_fac[0] = modinv(fac[0]);
    for(ll q=1; q<G; q++){
        fac[q] = (fac[q-1]*q)%mod;
        inv_fac[q] = modinv(fac[q]);
    }
    cin>>k;
    str t; cin>>t; a = t.size();
    k += a;
    ll all = binpow(26, k), pidori = 0;
    for(ll q=0; q<a; q++){
        pidori += CizNpoK(k, q)*binpow(25, k-q);
        pidori %= mod;
    }
    cout<<(all-pidori+mod)%mod;
}

Measured memory_bytes: 35564
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    long n, k;
    cin >> n >> k;
    int a[n], last[200001], next[n];
    fill(last, last+200001, -1);
    fill(next, next+n, 2000000);
    for (auto &ai:a) cin >> ai;
    for (int i=0; i<2*n; i++) {
        int ai = a[i % n];
        if (0 <= last[ai] && last[ai] < n && next[last[ai]] > i) next[last[ai]] = i + 1;
        last[ai] = i;
    }
    int cur = 0;
    long cnt = 0;
    vector<long> starts;
    do {
        starts.push_back(cnt);
        cnt += next[cur] - cur;
        cur = next[cur] % n;
    } while (cur > 0);
    auto st = prev(upper_bound(starts.begin(), starts.end(), (n * k) % cnt));
    for (int i=(*st % n); i<n; ) {
        if (next[i] <= n) {
            i = next[i];
            continue;
        }
        cout << a[i] << ' ';
        i++;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 5488
n = int(input())
s = input()

right_white = s.count(".")
left_black = 0

min_num = min(right_white, n-right_white)

for x in s:
    if x == ".":
        right_white -= 1
    else:
        left_black += 1

    min_num = min(min_num, right_white+left_black)

print(min_num)


Measured memory_bytes: 41948
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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; }

const int MAX = 100010;
int n;
ll m, a[MAX], b[MAX];
map<ll, ll> mp;

int main() {
    cin >> n >> m;
    rep(i, n) cin >> a[i];

    rep(i, n) b[i+1] = b[i] + a[i];
    rep(i, n+1) mp[b[i] % m]++;

    ll ans = 0;
    for (auto &x: mp) {
        ll num = x.second;
        if (num <= 1) continue;
        ans += num * (num - 1) / 2;
    }
    cout << ans << endl;
}


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

#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define eof !cin.eof()
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define ull unsigned long long
#define ll long long
#define ld long double
#define sz(a) a.size()
#define all(s) s.begin(), s.end()
#define rall(s, n) s, s + n
#define x first
#define y second
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ii pair <int, int>
#define iii pair <int, ii>
#define vi vector <int>
#define vit vector <int> :: iterator
#define vlt vector <ll> :: iterator
#define vl vector <ll> 
#define vii vector <ii>
#define viii vector <iii>
#define vd vector <double>
#define vull vector <ull>
#define vc vector <char>
#define vs vector <string>
#define vvi vector <vector <int>>
#define vvl vector <vector <ll>>
#define EPS 1e-10
#define INF 1000000000
#define mod 1000000007
#define reset(a, nilai) memset(a, nilai, sizeof(a))
#define minof min_element
#define maxof max_element
using namespace std;

int h, w;
int main () {
	IOS;
	
	scanf("%d%d", &h, &w);
	char G[h][w];
	for (int row = 0; row < h; row++) {
		scanf("%s", &G[row]);
	}
	vvi dp(h, vi (w));
	dp[0][0] = 1;
	for (int row = 0; row < h; row++) {
		for (int col = 0; col < w; col++) {
			for (int r2 = row; r2 <= row + 1; r2++) {
				int c2 = col;
				if (r2 == row) {
					c2 = col + 1;
				}
				if (r2 < h && c2 < w && G[r2][c2] == '.') {
					dp[r2][c2] = (dp[r2][c2] % mod + dp[row][col] % mod) % mod;
				}
			}
		}
	}
	printf("%d\n", dp[h - 1][w - 1]);
	return 0;
}

Measured memory_bytes: 5248
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long ll;

int main(){    
    int K;
    cin >> K;
    if(K <= 9) cout << K << endl;
    else{
        queue<ll> q;
        for(int i = 1; i <= 9; i++) q.push(i);
        int cnt = 9;
        while(true){
            ll a = q.front();
            ll b = a%10;
            if(b > 0){
                q.push(a*10+b-1);
                cnt++;
            }
            if(cnt==K) break;
            q.push(a*10+b);
            cnt++;
            if(cnt==K) break;
            if(b < 9){
                q.push(a*10+b+1);
                cnt++;
            }
            if(cnt==K) break;
            q.pop();
        }
        cout << q.back() << endl;
    }
}

Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Query {
    int type, a, b;
};

int main(){
    long long int n, q;
    string s;
    cin >> n >> s >> q;
    vector<Query> Q(q);
    for (int i=0; i<q; i++){
        cin >> Q[i].type;
        if (Q[i].type == 1){
            char c;
            cin >> Q[i].a >> c;
            Q[i].b = (int)c;
        }
        else {
            cin >> Q[i].a >> Q[i].b;
        }
    }
    vector<vector<int>> count(n+10);
    vector<int> _count(30, 0);
    vector<vector<int>> ans(q, vector<int>(30));
    count[0] = _count;
    for (int i=1; i<=n; i++){
        _count[s[i-1]-'a']++;
        count[i] = _count;
    }
    for (int i=0; i<q; i++){
        if (Q[i].type == 2){
            for (int j=0; j<30; j++){
                ans[i][j] = count[Q[i].b][j]-count[Q[i].a-1][j];
            }
        }
    }
    for (int i=0; i<q; i++){
        if (Q[i].type == 1){
            char org = s[Q[i].a-1], newc = Q[i].b;
            s[Q[i].a-1] = Q[i].b;
            for (int j=i+1; j<q; j++){
                if (Q[j].type == 2 && Q[j].a <= Q[i].a && Q[j].b >= Q[i].a){
                    ans[j][org-'a']--;
                    ans[j][newc-'a']++;
                }
            }
        }
        else {
            int _ans = 0;
            for (int j=0; j<30; j++){
                if (ans[i][j] != 0){
                    _ans++;
                }
            }
            cout << _ans << endl;
        }
    }
    return 0;
}

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

using namespace std;

long long dp[2][4096];

int n,m;

int a[1001];
int mask[1001];

int main() {
   
   cin>>n>>m;
   
   for(int i=0;i<m;i++){
       int b;
       
       cin>>a[i]>>b;
       
       int curr=0;
       
       for(int j=0;j<b;j++){
           int x;
           cin>>x;
           x--;
           curr+=(1<<x);
       }
       
       
       mask[i]=curr;
   }
   
   for(int i=0;i<2;i++)
    for(int j=0;j<4096;j++)
        dp[i][j]=100000001;
   
  
   
   dp[0][0]=0;
   dp[0][mask[0]]=a[0];
   
   for(int i=1;i<m;i++){
       
       for(int j=0;j<(1<<n);j++){
           dp[1][j]=dp[0][j];
       }
       
       for(int j=0;j<(1<<n);j++){
           
           if(dp[0][j]!=100000001){
           dp[1][mask[i]|j]=min(dp[1][mask[i]|j],dp[0][j]+a[i]);
           
           }
           
       }
       
       for(int j=0;j<(1<<n);j++){
           dp[0][j]=dp[1][j];
       }
       
   }
   
   
   
   if(dp[0][(1<<n)-1]!=100000001)
   cout<<dp[0][(1<<n)-1];
   else
   cout<<-1;
   
   
}

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

int main() {
    int n;
    int p[20];
    int count = 0;

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> p[i];
        if (i > 1){
            int p_min = min(p[i - 2], p[i]);
            int p_max = max(p[i - 2], p[i]);
            if (p_min < p[i-1] && p_max > p[i-1]) count++;
        }
    }
    cout << count << endl;
}

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


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;
typedef long long int ll;
ll dp[1005][1005];

// typedef vector<int> vi;
// typedef vector<vi> vvi;
// typedef queue<int> qi;
int main()
{
    ll mod = 1000000007;
    int h, w;
    cin >> h >> w;

    char state[h][w];
    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            cin >>state[i][j];
            // if(state[i][j]==".")
            //     dp[i][j] = 0;
            // else dp[i][j] = -1;
        }
    }

    for(int hi = h-1; hi>=0; hi--)
    {
        for(int wi= w-1; wi>=0; wi--)
        {   
            // dp[wi][hi] = 1;

            if(state[hi][wi]=='.'){
                dp[hi][wi] = (dp[hi][wi+1] + dp[hi+1][wi])%mod;
            }
            if(wi==w-1 && hi==h-1) dp[hi][wi] = 1;

            // cout <<dp[wi][hi] << " ";

        }
        // cout<<endl;
    }
    // for(int i=0; i<h; i++)
    
    // {
    //     for(int j=0; j<w; j++)
    //     { 
    //         cout<< dp[i][j]<< " ";
    //     }
    //     cout << endl;
    // }

    cout<<dp[0][0]%mod<<endl;
    return 0;
}

Measured memory_bytes: 9088
N = int(input())
AB = [tuple(map(int,input().split())) for _ in range(N)]

X = []
for (a,b) in AB:
    X.append((a+b,b))

X.sort(reverse=True)
pa,pb = 0,0
for i in range(N):
    ab,b = X[i]
    pb += b
    if i%2==0:
        pa += ab

print(pa-pb)

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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define For(i, a, b) for (ll i = (a); i < (b); i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N;
    cin >> N;
    int H[N];
    rep(i, N) cin >> H[i];
    int ans = 0;
    rep(i, N - 1) if (H[i] > H[i + 1]) ans += H[i] - H[i + 1];
    ans += H[N - 1];

    cout << ans << endl;





    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#define int long long
using namespace std;

int calc(int a,int x){
	if(a == -1) return -1;
	return a / x;
}

signed main(){
	int a,b,x;
	cin >> a >> b >> x;
	cout << calc(b,x) - calc(a - 1,x) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long int64;
static const int MAXN = 1e5 + 4;

int n, a[MAXN];
char op[MAXN];
int64 f[MAXN][3];

int main()
{
    scanf("%d%d", &n, &a[0]);
    for (int i = 1; i < n; ++i) {
        scanf(" %c %d", &op[i], &a[i]);
        if (op[i] == '-') a[i] = -a[i];
    }

    memset(f, 0x80, sizeof f);
    f[0][0] = a[0];
    for (int i = 1; i < n; ++i) {
        f[i][2] = f[i - 1][2] + a[i];
        f[i][1] = std::max(f[i][2], f[i - 1][1] - a[i]);
        f[i][0] = std::max(f[i][1], f[i - 1][0] + a[i]);
        if (a[i] < 0) {
            f[i][1] = std::max(f[i][1], f[i - 1][0] + a[i]);
            f[i][2] = std::max(f[i][2], f[i - 1][1] - a[i]);
        }
    }

    printf("%lld\n", std::max(std::max(f[n - 1][0], f[n - 1][1]), f[n - 1][2]));
    return 0;
}


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

using namespace std;

#define chmin(a,b) a=min(a,b)
#define rep(i,x) for(int i=0;i<(x);++i)

const int inf = 1e9;

int N, M;
int mc[100][100], mt[100][100];

int main()
{
	while (scanf("%d %d", &N, &M), N || M) {
		fill(mc[0], mc[M], inf);
		fill(mt[0], mt[M], inf);

		rep(i, M) mc[i][i] = mt[i][i] = 0;

		rep(i, N) {
			int a, b, cost, time; scanf("%d %d %d %d", &a, &b, &cost, &time); a--; b--;
			mc[a][b] = mc[b][a] = cost;
			mt[a][b] = mt[b][a] = time;
		}

		rep(k, M) rep(i, M) rep(j, M) {
			chmin(mc[i][j], mc[i][k] + mc[j][k]);
			chmin(mt[i][j], mt[i][k] + mt[j][k]);
		}

		int K; scanf("%d", &K);
		rep(i, K) {
			int p, q, r; scanf("%d %d %d", &p, &q, &r); p--; q--;
			printf("%d\n", r == 0 ? mc[p][q] : mt[p][q]);
		}
	}
}

Measured memory_bytes: 1104
#include "stdio.h"
int main(int argc, char const *argv[])
{
	int num[101][101],i,j,k,r,c;
	scanf("%d",&r); scanf("%d",&c);
	for(i=0;i<r;i++){
		for(j=0;j<c;j++)
			scanf("%d",&num[i][j]);
	}
	for(i=0;i<r;i++){
		num[i][c]=0;
		for(j=0;j<c;j++)
			num[i][c] = num[i][c] + num[i][j];
	}
	for(i=0;i<c;i++){
		num[r][i]=0;
		for(j=0;j<r;j++)
			num[r][i] = num[r][i] + num[j][i];
	}
	num[r][c] = 0;
	for(i=0;i<r;i++)
		num[r][c] = num[r][c] + num[i][c];

	for(i=0;i<=r;i++){
		for(j=0;j<=c;j++){
			printf("%d",num[i][j]);
			if(j != c)
				printf(" ");
			else
				printf("\n");
		}

	}
	return 0;
}


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

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    
    // a*c or a*d or b*c or b*d
    ll ans = a * c;
    if (ans < a * d){
        ans = a * d;
    }
    if (ans < b * c){
        ans = b * c;
    }
    if (ans < b * d){
        ans = b * d;
    }

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

Measured memory_bytes: 3628
#include"bits/stdc++.h"
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(x) x.begin(),x.end()

using namespace std;
typedef long long ll;

template<typename T>
T gcd(T a, T b) {
    if (a % b == 0) {
        return(b);
    }
    else {
        return(gcd(b, a % b));
    }
}

template<typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

int main(void) {
    ll ans = 0;
    ll n;
    cin >> n;
    vector<ll>a(n);
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n - 1) {
        if (a[i] > a[i + 1]) {
            ans += a[i] - a[i +1 ];
            a[i + 1] = a[i];
        }
    }
    cout << ans;
}

/*
*/


Measured memory_bytes: 4780
def dot(vx1, vy1, vx2, vy2):
    return vx1*vx2 + vy1*vy2


def cross(vx1, vy1, vx2, vy2):
    return vx1*vy2 - vy1*vx2


q = int(input())

for _ in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())

    c1 = cross(x1 - x0, y1 - y0, x2 - x0, y2 - y0)
    c2 = cross(x1 - x0, y1 - y0, x3 - x0, y3 - y0)
    c3 = cross(x3 - x2, y3 - y2, x0 - x2, y0 - y2)
    c4 = cross(x3 - x2, y3 - y2, x1 - x2, y1 - y2)
    d1 = dot(x1 - x0, y1 - y0, x2 - x0, y2 - y0)
    d2 = dot(x1 - x0, y1 - y0, x3 - x0, y3 - y0)
    d3 = dot(x0 - x1, y0 - y1, x2 - x1, y2 - y1)
    d4 = dot(x0 - x1, y0 - y1, x3 - x1, y3 - y1)

    if c1*c2 <= 0 and c3*c4 <= 0:
        if (d1 < 0 and d2 < 0) or (d3 < 0 and d4 < 0):
            print(0)
        else:
            print(1)
    else:
        print(0)



Measured memory_bytes: 5628
#include <iostream>
#include <algorithm>
#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 = unsigned;
using u64 = unsigned long long;
using namespace std;

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    int an = INF<int>;
    for (int i = 0; i <= v[0]; ++i) {
        auto a = v;
        a[0] -= i;
        int ans = i;
        for (int j = 0; j+1 < n; ++j) {
            ans += max(0, a[j])*2;
            a[j+1] -= max(0, a[j]);
        }
        ans += max(0, a.back());
        an = min(an, ans);
    }
    cout << an << "\n";
    return 0;
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define deb(...) 42
#endif

ll lazy[(1 << 21)];


void update(int v, int tl, int tr, int l, int r, ll val, bool state = false){
    if(l > r)   return;
    else if(tl == l and tr == r){
        lazy[v] = min(lazy[v], val);
    }
    else{
        int tm = (tl + tr) /2;
        if(state)   deb(v, tl, tr, l, r);
        update(v*2, tl, tm, l, min(tm, r), val);
        update(v*2 + 1, tm + 1, tr, max(tm + 1, l), r, val);
    }
}

ll get(int v, int tl, int tr, int pos){
    if(tl == tr)    return lazy[v];
    else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)   return min(lazy[v], get(v*2, tl, tm, pos));
        else    return min(lazy[v], get(v*2 + 1, tm + 1, tr, pos)); 
    }
}

main(){    
    #ifdef XOX
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> arr(n + 1);

    fill_n(lazy, 4*n + 10, INF);
    
    int l, r;
    ll c;
    for(int i = 0; i < m; i++){
        cin >> l >> r >> c;
        arr[l].push_back({r, c});
    }

    update(1, 1, n, 1, 1, 0ll);
    for(int i = 1; i < n; i++){
        ll cur = get(1, 1, n, i);
        for(auto x : arr[i]){
            update(1, 1, n, i + 1, x.first, cur + x.second);
        }
    }


    if(get(1, 1, n, n) == INF)  cout << -1;
    else    cout << get(1, 1, n, n);
}

Measured memory_bytes: 9728
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 50;


ll a[MAX_N];
ll solve (int n, int m ){	// 最大数 n までの数 m: a[] の個数
	ll res = 0LL;
	for (int i = 1; i < (1<<m); i++ ){
		int num = 0;
		for (int j = i; j != 0; j >>=1 ) num += j & 1;	// i の立っているビットの個数
		ll lcm = 1LL;
		rep (j, m ){
			if (i & (1<<j) ){
				lcm = lcm/__gcd (lcm, a[j] )*a[j];
				// lcm が n を超えると n/lcm = 0 なので オーバーフローする前に break する
				if (lcm > n ) break;
			} // end if
		} // end rep
		if (num % 2 == 0 ) res -= n / lcm;
		else res += n / lcm;
	} // end for

	return res;
}

ll solve2 (int n, int m ){	// 最大数 n までの数 m: a[] の個数
	ll res = 0LL;
	for (int i = 1; i < (1<<m); i++ ){
		int num = 0;
		for (int j = i; j != 0; j >>=1 ) num += j & 1;	// i の立っているビットの個数
		ll lcm = 1LL;
		rep (j, m ){
			if (i & (1<<j) ){
				lcm = lcm/__gcd (lcm, a[j] )*a[j];
				// lcm が n を超えると n/lcm = 0 なので オーバーフローする前に break する
				if (lcm > n ) break;
			} // end if
		} // end rep
		if (num % 2 == 0 )
			res -= ((ll)n/lcm)*(lcm+(ll)n)/2LL;
		else
			res += ((ll)n/lcm)*(lcm+(ll)n)/2LL;
	} // end for

	return res;
}

double ans (int n, int m ){

	ll cnt = (ll)n - solve (n, m );
	ll sum = (ll)n*(n+1LL)/2LL - solve2 (n, m );

	if (cnt == 0 ) return 0.;
	double res = (double)sum/(double)cnt;

	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	int n, m;
	while (cin >> n >> m, n ){
		memset (a, 0, sizeof (a ) );
		rep (i, m ) cin >> a[i];
		double res = ans (n, m );
		printf ("%.9lf\n", res );
	} // end while
	
	return 0;
}

Measured memory_bytes: 1252
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define MOD 1000000007LL

using namespace std;
using llong = long long;

int main()
{
	IOS;
	
	int n, m;
	cin >> n >> m;
	int i;
	set<string> ac;
	int pen = 0;
	int accnt = 0;
	
	map<string, int> penpen;
	for (i = 1; i <= m; i++)
	{
		string p, acwa;
		cin >> p >> acwa;
		if (ac.count(p) == 0 && acwa == "WA") penpen[p]++;
		else if (ac.count(p) == 0 && acwa == "AC")
		{
			accnt++;
			if (penpen.count(p) != 0) pen += penpen[p];
			ac.insert(p);
		}
	}
	cout << accnt << " " << pen;
	return 0;	
}



Measured memory_bytes: 11400
#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
typedef pair<string, int> si;
const int N = 1e5 + 5;
int n, q, k, cnt[26][26], cntPre = 0, pos[26], finalAns[N];
string s[N];
vector<si> queries[N];
struct Trie {
	struct Node {
		int child[26], sz, fin;
		Node() {
			memset(child, -1, sizeof child);
			sz = 0;
			fin = -1;
		}
	} t[N << 2];
	int sz = 1;
	void add(string &s, int id) {
		int cur = 0;
		fw (i, 0, s.length()) {
			int cha = s[i] - 'a';
			if (t[cur].child[cha] == -1) {
				t[cur].child[cha] = sz;
				sz++;
			}
			t[cur].sz++;
			cur = t[cur].child[cha];
		}
		t[cur].sz++;
		t[cur].fin = id;
	}
	void dfs(int id) {
		int curNode = 0;
		fw (i, 0, s[id].length()) {
			if (t[curNode].fin != -1) cntPre++;
			int cha = s[id][i] - 'a';
			fw (j, 0, 26) if (t[curNode].child[j] != -1) {
				cnt[cha][j] += t[t[curNode].child[j]].sz;
			}
			curNode = t[curNode].child[cha];
		}
	}
} trie;
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 0, n) cin >> s[i], trie.add(s[i], i);
	cin >> q;
	fw (i, 0, q) {
		int k;
		string order;
		cin >> k >> order;
		k--;
		queries[k].pb(si(order, i));
	}
	fw (i, 0, n) {
		memset(cnt, 0, sizeof cnt);
		cntPre = 0;
		trie.dfs(i);
//		cout << "i = " << i << "\n";
//		fw (j, 0, 26) fw (k, 0, 26) if (cnt[j][k]) cout << "Cnt[" << char(j + 'a') << "][" << char(k + 'a') << "] = " << cnt[j][k] << "\n";
		fa (lol, queries[i]) {
			string j = lol.fi;
			int queryID = lol.se;
			fw (k, 0, j.length()) pos[j[k] - 'a'] = k;
			int ans = cntPre;
			fw (k, 0, 26) fw (l, 0, 26) {
				//For all characters k what's the answer
				if (pos[l] < pos[k]) ans += cnt[k][l];
			}
			finalAns[queryID] = ans;
		}
	}
	fw (i, 0, q) cout << finalAns[i] + 1 << "\n";
	return 0;
}

Measured memory_bytes: 61824
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
int main()
{
    int N;
    cin >> N;

    cout << (N+1)/2 << endl;

   return 0;
}

Measured memory_bytes: 256
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		int N = nextInt();
		if(N == 3 || N == 5 || N == 7){
			myout("YES");
		}else{
			myout("NO");
		}
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 32912
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N;
	cin>>N;
	int ans = 1;
	rep(i,N){
		ans *= 2;
		if(N<ans){cout<<ans/2<<endl; return 0;}
	}
	return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e15;
const ll MOD = 1e9+7;
const ll LINF = 1e18;


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  double a; cin>>a;
  double ans=2*a*3.1415926;
  cout<<ans<<endl;
}

Measured memory_bytes: 3800
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int formula();
int p;
string s;

int main(){
  int n;  
  cin>>n;
  while(n--){
    cin>>s;
    p=0;
    cout<<formula()<<endl;
  }
  return 0;
}

int formula(){
  int res=0,f=0;
  vector<int> v;
  while('0'<=s[p]&&s[p]<='9') res=res*10+s[p]-'0',p++,f=1;
  if(f){
    res=res/2+1;
    return res;
  }
  while(s[p]=='[') p++,v.push_back(formula()),p++;
  if(!f){
    sort(v.begin(),v.end());
    for(int i=0;i<v.size()/2+1;i++) res+=v[i];
  }
  return res;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype (i)=(j);(i)<=(k);(i)++)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
#define ppii pair<int,pii >
const int inf=0x3f3f3f3f,
mod=1000000007;
const double pi=3.1415926535897932,
eps=1e-6;
int n,m,f[100005][3],s,t;bool vis[100005][3];vector<int> v[100005];queue<ppii > q;
void bfs(int x){
    q.push(mpr(x,mpr(0,0)));
    while(!q.empty()){
        ppii w=q.front();q.pop();
        rep(i,0,(int)v[w.fi].size()-1){
            int to=v[w.fi][i],mo=(w.se.fi+1)%3,stp=w.se.se+1;
            if(vis[to][mo]) continue;
            vis[to][mo]=1;f[to][mo]=stp;q.push(mpr(to,mpr(mo,stp)));
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        v[t1].pb(t2);
    }
    scanf("%d%d",&s,&t);
    bfs(s);
    if(!vis[t][0]) puts("-1");
    else printf("%d\n",f[t][0]/3);
    return 0;
}

Measured memory_bytes: 7168
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6 + 5;
double a[N];
long long  n, k;
double round(double r)
{
    return floor(r + 0.5);
}
bool Check(double x) {
    long long cnt = 0;
    for(int i = 1; i <= n; ++i) {
        /*cnt += a[i]/x;
        if(floor(a[i]/x)*x == a[i]) --cnt;*/
        cnt += ceil(a[i]/x) - 1;
        if(cnt > k) return false;
    }
    return true;
}
int main() {
    cin >> n >> k;
    double Max = -1;
    for(int i = 1; i <= n; ++i) { 
        scanf("%lf",&a[i]);
        //if(a[i] > Max) Max = a[i];
        //if(a[i] < Min) Min = a[i];
    }
    double L = 0, R = 1e9 + 5, Mid;
    for(int i = 1; i <= 200; ++i) {
        Mid = (L+R)/2;
        if(Check(Mid)) R = Mid;
        else L = Mid;
    }
    Mid =(L+R)/2;
    //printf("%f\n",Mid);
    printf("%d\n",int(ceil(Mid)));
return 0;
}

Measured memory_bytes: 5356
md = 1000000000 + 7

def fi(n):
  if n < 0:
    return 0
  elif n <= 1:
    return 1
  elif n == 2:
    return 2
  else:
    return ( fi(n-1) + fi(n-2) ) % md


h, w, k = map(int, input().split())
li = [0 for i in range(w)]

li[0] = 1

li_prev = []
li_next = []

li_prev[:] = li[:]
li_next[:] = li[:]

for j in range(h):
  for i in range(w):
    li_next[i] = (li_prev[max(0,i-1)] * fi(i-1) * fi(w-i-1)
               + li_prev[i] * fi(i) * fi(w-i-1)
               + li_prev[min(w-1,i+1)] * fi(i) * fi(w-i-2)) % md
  li_prev[:] = li_next[:]

print(li_prev[k-1])

Measured memory_bytes: 3064
#include <stdio.h>
 
long long gcd(long long x,long long y){
  long long r;
  if(x>y){
    long long t = y;
    y = x;
    x = t;
  }
  while((r = y % x) != 0){
    y = x;
    x = r;
  }
  return x;
}
 
int main(){
  long long T[100],ans=1,sp;
  int i,j,N;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%lld",&T[i]);
  }
  for(i=0;i<N-1;i++){
    for(j=N-1;j>i;j--){
      if(T[j]>T[j-1]){
      sp=T[j];
      T[j]=T[j-1];
      T[j-1]=sp;
      }
    }
  }
  ans = T[0];
  for(i=1;i<N;i++){
    if(ans%T[i]==0){
      continue;
    }
      else{
      ans = ans/gcd(ans,T[i])*T[i];
      }
  }
  printf("%lld",ans);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

int main(){
    int n;
    cin >> n;
    for(int j=0;j<n;j++){
        int t;
        cin >> t;
        vector<int> blocks(t);
        for(int i=0;i<t;i++) cin >> blocks[i];

        int now = blocks[0];
        int upmax=0,downmax=0;
        for(int i=0;i<t;i++){
            if(now > blocks[i]){
                downmax = max(downmax,now-blocks[i]);
            }else if(now < blocks[i]){
                upmax = max(upmax,blocks[i]-now);
            }
            now = blocks[i];
        }
        cout << upmax << " " << downmax << endl;
    }
    return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
int dist[101][101];
int n, m;
bool isUsed(int a, int b, int c){
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(dist[i][j] == dist[i][a] + c + dist[b][j]) return false;
    }
  }
  return true;
}
int main(){
  cin >> n >> m;
  for(int i=0; i<n; i++) for(int j=0; j<n; j++) dist[i][j] = (i == j ? 0 : 1e9);
  vector<int> a(m), b(m), c(m);
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i] >> c[i];
    dist[--a[i]][--b[i]] = c[i];
    dist[b[i]][a[i]] = c[i];
  }
  for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  int ans = 0;
  for(int i=0; i<m; i++) ans += isUsed(a[i], b[i], c[i]);
  cout << ans << endl;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define mt make_tuple
#define popb pop_back
#define popf pop_front
#define int long long int
#define vi         vector<int>
#define vll        vector<ll>
#define vpii       vector<pair<int,int>>
#define vpll       vector<pair<ll,ll>>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(container) int((container).size())
#define rep(i,a,b) for(i=a;i<b;i++)
#define tr(container,it)   for(auto it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())      //set,map etc.
#define cpresent(container, element) (find(all(container),element) != container.end())    //vector
#define hell 1000000007
#define b32 2147483647
#define PI 3.14159265
#define mod 998244353
#define fs first
#define sc second
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
void solve()
{
  int n,i,j,sum=0;
  cin>>n;
  vector<int>v(n);
  int p[n];
  rep(i,0,n)
  {
    cin>>v[i];
    p[0]=v[0];
    p[i]=p[i-1]+v[i];
  }
  int dp[n][n];
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
      dp[i][j]=1e18;
  }
  for(i=n-1;i>=0;i--)
  {
    for(j=i;j<n;j++)
    {
      if(i==j)
        dp[i][j]=0;
      else
      {
        if(i-1>=0)
          sum=p[j]-p[i-1];
        else
          sum=p[j];
        for(int k=i;k<=j-1;k++)
        {
          dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum);
        }
      }
    }
  }
  cout<<dp[0][n-1];
}
signed main()
{
  fastio
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  int t;
  t=1;
  //cin>>t;
  while(t--)
  solve();
  TIME
  return 0;
}

Measured memory_bytes: 1536
N = int(input())

d = {'M':0,'A':0,'R':0,'C':0,'H':0}

for i in range(N):
    s = input()
    if s[0] in 'MARCH':
        d[s[0]]+=1

v = list(d.values())
ans = 0

for i in range(5):
    for j in range (i+1,5):
        for k in range (j+1,5):
            ans += v[i]*v[j]*v[k]

print(ans)

Measured memory_bytes: 3064
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number == color[V]:
            number += 1
        color[v] = number
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])


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

int main() {
  ll n;
  cin >> n;
  
  ll ans=0;
  
  for(ll i=1; i<n+1; i++){
   if(i%3!=0 && i%5!=0) ans+=i;
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
#include <numeric>



typedef long long ll;


using namespace std;

typedef pair<int, int> P;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)



ll fast_pow(ll x,ll n,ll mod){
    if (n==0) return 1;
    ll res=fast_pow(x*x %mod,n/2,mod);
    if (n&1) res=res*x%mod;
    return res;
}

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;




int main(){
    int a;
    float b;
    cin>>a>>b;
    cout<<int(ceil(a/(2*b+1)))<<endl;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  cin >> s;
  
  vector<string> t = {"KIHBR", "KIHBRA", "KIHBAR", "KIHBARA", 
                      "KIHABR", "KIHABRA", "KIHABAR", "KIHABARA", 
                      "AKIHBR", "AKIHBRA", "AKIHBAR", "AKIHBARA", 
                      "AKIHABR", "AKIHABRA", "AKIHABAR", "AKIHABARA"};
  bool flag = false;
  for (int i = 0; i < 16; i++) {
    if (s == t.at(i)) flag = true;
  }
  
  if (flag) cout << "YES\n";
  else cout << "NO\n";
}

Measured memory_bytes: 256
N = int(input())
S = input()
alphabet = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
alphabet_dicts = {}
for i, al in enumerate(alphabet):
    alphabet_dicts[al] = i
S_dush = alphabet[N:]+alphabet[:N]
ans = ""
for s in S:
    ans += S_dush[alphabet_dicts[s]]
print(ans)
print()

Measured memory_bytes: 3060
#include <stdio.h>

int main(void){
    int a, b, c, d;
    scanf("%d %d %d\n", &a, &b, &c);
    if(b>c){
        d=b;
        b=c;
        c=d;
    }
    if(a>b){
        d=a;
        a=b;
        b=d;
    }
    if(b>c){
        d=b;
        b=c;
        c=d;
    }
    printf("%d %d %d\n", a, b, c);
}


Measured memory_bytes: 2676
#include <stdio.h>

#define MAX 500000
#define SENTINEL 2000000000/*教科書の無限大*/

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left, int mid, int right) {
  int i, j, k;/*k=統合*/
  int n1 = mid -left;
  int n2 = right - mid;
  for(i=0;i<n1;i++) L[i] = A[left + i];
  for(i=0;i<n2;i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i=0, j=0;
  for(k=left; k<right; k++) {
    cnt++;
    if(L[i]<=R[j]) {/*以下にする理由安定なソートであるため*/
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right) {
  int mid;
  if(left+1 < right) {
    mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int main(void) {
  int A[MAX], n, i;
  cnt = 0;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);

  mergeSort(A, n, 0, n);
  for(i=0;i<n;i++) {
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n%d\n",cnt);

  return 0;
}


Measured memory_bytes: 5692
#include<bits/stdc++.h>
using namespace std;
char a[52],b[52];
int main(){
    cin>>a;
    cin>>b;
    int la=strlen(a),lb=strlen(b);
    int l=min(la, lb), ll=max(la, lb);
    for(int i=0;i<=l-1;i++) cout<<a[i]<<b[i];
    if(la>lb) for(int i=l;i<=ll-1;i++) cout<<a[i];
    else for(int i=l;i<=ll-1;i++) cout<<b[i];
    return 0;
}

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

fn main() {
    let s = read::<String>();
    let cs = s.chars().collect::<Vec<char>>();

    if cs[2] == cs[3] && cs[4] == cs[5] {
        println!("Yes");
    } else {
        println!("No");
    }
}

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

vector<vector<int>> DF(150, vector<int>(150,0));
vector<int> color(150,0);
int tt=0;
vector<int> F(150), D(150);
int n;
# define WHITE 0
# define GRAY 1
# define BLACK 2




void dfs_visit(int u){
    F[u] = ++tt;
    color[u]=GRAY;
    rep(i,n){
        if(DF[u][i]==1 && color[i]==WHITE){
            dfs_visit(i);
        }
    }
    color[u]==BLACK;
    D[u]=++tt;
}

void dfs(){
    rep(u,n){
        if(color[u]==WHITE)dfs_visit(u);
    }
}

int main(){
    cin >> n;
    vector<list<int>>  L(n);
    rep(i,n){
        int u, e;
        cin >> u>>e;
        rep(j,e){
            int v;cin>>v;--v;
            L[i].push_back(v);
        }
    }
    rep(i,n){
        rep(j,n){
            list<int>::iterator it = find(L[i].begin(),L[i].end(),j);
            if(it!=L[i].end()){
                DF[i][j]=1;
                L[i].erase(it);
            }
        }
    }
    dfs();
    rep(i,n){
        printf("%d %d %d\n",i+1,F[i],D[i]);
    }
    return 0;
}


Measured memory_bytes: 3316
import heapq
k = int(input())

a = [i for i in range(1, 10)]
heapq.heapify(a)
ans = 0
while ans < k:
    r = heapq.heappop(a)
    ans += 1
    if ans == k:
        print(r)
        break
    for i in [-1, 0, 1]:
        if r % 10 + i < 0 or 9 < r % 10 + i:
            pass
        else:
            heapq.heappush(a, int("{}{}".format(r, r % 10 + i)))


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    string S;
    int w;
    cin >> S >> w;
    string ans;
    rep(i,0,S.size()) if(i%w==0) ans+=S[i];

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    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(){

	int k;
	vector<int> v(5);
	rep(i,5) scanf("%d", &v[i]);
	scanf("%d", &k);
	
	rep(i,5){
		rep(j,5){
			if (abs(v[i]-v[j]) > k){
				cout <<":(\n";
				return 0;
			} 
		}
	}
	cout << "Yay!\n";
	return 0;
}


Measured memory_bytes: 3700