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

long long N;

long long dfs(string s) {
  if(stoll(s) > N) return 0;

  long long ret = 0;

  bool three = false, five = false, seven = false;
  for(char sub: s) {
    if(sub == '3') three = true;
    if(sub == '5') five = true;
    if(sub == '7') seven = true;

    if(three && five && seven) {
      ret++;
      break;
    }
  }

  for(string sub: {"3", "5", "7"}) {
    ret += dfs(s+sub);
  }

  return ret;
}

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

  cin >> N;
  cout << dfs("0") << endl;

  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >>n;
  int l=to_string(n).size();
  if(l==1) cout <<n;
  else if(l==2) cout <<9;
  else if(l==3) cout <<n-90;
  else if(l==4) cout <<909;
  else if(l==5) cout <<n-9090;
  else cout <<90909;
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
  int n; cin>>n;
  vll h(n); rep(i,n) cin>>h[i];
  int cnt=0;
  int ans=0;
  rep(i,n-1){
    if(h[i]>=h[i+1]&&i<n-2) cnt++;
    else{
      if(h[i]>=h[i+1]) cnt++;
      ans=max(ans,cnt);
      cnt=0;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 4036
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
	#define SAY(X) cout << (X) << '\n';
#else
	#define DBG(X)
	#define SAY(X)
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for(auto& elem: ret) cin >> elem; return ret; }

const int MAXN = (int)2e5 + 77;
int p[MAXN], n, k;
ll answ = 0;

void solve() {
	cin >> n >> k;

	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		p[i] += k - 1;
		p[i] %= k;

		p[i] += p[i - 1];
		p[i] %= k;
	}

#ifdef __LOCAL
	for(int i = 0; i <= n; ++i) {
		cout << p[i] << ' ';
	}

	cout << '\n';
#endif

	map<int, int> cnt;

	for(int r = 0; r <= n; ++r) {
		answ += cnt[p[r]];

		if(r >= k - 1) {
			--cnt[p[r - k + 1]];
		}

		++cnt[p[r]];
	}

	cout << answ << '\n';
}

int main() {
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 10368
#include <stdio.h>
int main()
{
	int a[10001],i,k;
	i = 1;
	while (1) {
		scanf("%d",&a[i]);
		if (a[i] == 0) {break; }
		else { i++; }
	}
	k = 1;
	while (1) {
		if (a[k] != 0) { printf("Case %d: %d\n",k, a[k]); k++; }
		else { break; }
	}
	return 0;
}



Measured memory_bytes: 2640
object Main extends App {
  import scala.io.StdIn._

  val Array(h, w) = readLine.trim.split(' ').map(_.toInt)
  val Array(a, b) = readLine.trim.split(' ').map(_.toInt)
  println(
    h * w - (h - (h % a)) * (w - (w % b))
  )
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline
    def let[A](func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 44156
from itertools import product

ss = input()
ans = []
for pattern in product(range(2),repeat=len(ss)-1):
    if sum(list(pattern)) is 0:
        continue
    tmp = ''
    for s,p in zip(ss,pattern):
        tmp += s
        if p == 1:
            tmp += '+'
    tmp += ss[-1]
    ans.append(eval(tmp))
print(sum(ans)+int(ss))


Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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




template <typename T>
class dijkstra
{
private:
    using P = pair<T, T>;
    struct edge{
        long long to;
        T cost;
    };
    long long vertex;   // 頂点数
    vector<vector<edge>> list;  //隣接リスト
    vector<T> distance;    // 距離
public:
    dijkstra(long long n, T infinity = 1e16);  // nは頂点の数、infinityは初期化に使う値
    void add_edge(long long v1, long long v2, T cost);    // 頂点v1から頂点v2に辺を張る
    void run(long long s);        // sは開始地点。
    T get_distance(long long v);    // 頂点vへの距離を返す
};

template <typename T>
dijkstra<T>::dijkstra(long long n, T infinity){
    vertex = n;
    list.resize(n);
    distance = vector<T>(vertex, infinity);
}

template <typename T>
void dijkstra<T>::add_edge(long long v1, long long v2, T cost){
    list[v1].push_back({ v2, cost });
}

template <typename T>
void dijkstra<T>::run(long long s){
    priority_queue<P, vector<P>, greater<P>> que;
    
    distance[s] = 0;    // 開始点の距離は0
    que.push(P(0, s));
    
    while(!que.empty()){
        P p = que.top(); que.pop();
        T v = p.second;
        if(distance[v] < p.first) continue;
        for(auto e : list[v]){
            if(distance[e.to] > distance[v] + e.cost){
                distance[e.to] = distance[v] + e.cost;
                que.push(P(distance[e.to], e.to));
            }
        }
    }
}

template <typename T>
T dijkstra<T>::get_distance(long long v){
    return distance[v];
}

int main() {
    ll n, m, s, t;
    cin >> n >> m >> s >> t;
    s--;t--;
    
    dijkstra<ll> dik1(n, INF), dik2(n, INF);
    REP(i, m){
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;v--;
        
        dik1.add_edge(u, v, a);
        dik1.add_edge(v, u, a);
        dik2.add_edge(u, v, b);
        dik2.add_edge(v, u, b);
    }
    
    dik1.run(s);
    dik2.run(t);
    
    vector<ll> ans(n);
    ans[n - 1] = 1e15 - (dik1.get_distance(n - 1) + dik2.get_distance(n - 1));
    for(ll i = n - 2; i >= 0; i--){
        ans[i] = max(ans[i + 1], (ll)1e15 - (dik1.get_distance(i) + dik2.get_distance(i)));
    }
    
    REP(i, n){
        cout << ans[i] << '\n';
    }
}

Measured memory_bytes: 19012
#include<cstdio>
#include<cctype>
#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define Chkmax(a,b) a=a>b?a:b
#define Chkmin(a,b) a=a<b?a:b
using namespace std;
template<typename T>inline void read(T &x)
{
	T s=0,f=1;static char c;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())s=s*10+(c^48);
	x=s*f;
}
static long long a,b,c,x,y;
inline void init()
{
	read(a);read(b);read(c);read(x);read(y);
}
static int ans;
inline void solve()
{
	static long long minu=min(x,y);x-=minu;y-=minu;
	if(2*c<a)a=2*c;if(2*c<b)b=2*c;
	if(c*2ll<=a+b)printf("%lld\n",2ll*minu*c+x*a+y*b);
	else printf("%lld\n",minu*(a+b)+x*a+y*b);
}
int main()
{
	init();
	solve();
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#define rep(i,n) for(int i=0;i<(int)n;i++)

using namespace std;


int main()
{
	int n;
	cin>>n;
	for(;n!=0;cin>>n)
	{
		int a[10]={};
		rep(i,n)
		{
			int x;
			cin>>x;
			a[x]++;
		}
		
		rep(i,10)
		{
			if(a[i]==0)
			{
				cout<<"-"<<endl;
				continue;
			}
			rep(k,a[i])
			{
				cout<<"*";
			}
			cout<<endl;
			
		}
		
	}
}

Measured memory_bytes: 1152
/*B - 81*/

#include <bits/stdc++.h>

using namespace std;

int main(){

	int n;
	int x;
	bool can = false;

	cin >> n;

	for (int i = 1; i <= 9; ++i)
	{
		x = n / i;
		if(i * x == n and x < 10){
			can = true;
			break;
		}
	}

	if(can)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(q), b(q), c(q), d(q);
    rep(i, q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }

    vector<int> p(n + m - 1, 1);
    vector<int> v;
    rep(i, n) p[i] = 0;
    int ans = 0;
    do {
        int now = 1;
        v.clear();
        for (int i = 0; i < n + m - 1; i++) {
            if (p[i] == 0)
                v.push_back(now);
            else
                now++;
        }
        int cnt = 0;
        rep(i, q) {
            if (v[b[i]] - v[a[i]] == c[i]) cnt += d[i];
        }
        chmax(ans, cnt);
    } while (next_permutation(all(p)));
    cout << ans << endl;
}

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

int main(){
  int N, M;
  cin>>N>>M;
  vector<vector<int>> data(M, vector<int>(2));
  for(int i=0;i<M;i++){
    for(int j=0;j<2;j++){
      cin>>data.at(i).at(j);
    }
  }
  vector<int> ans(N);
  for(int i=0;i<M;i++){
    for(int j=0;j<2;j++){
      ans.at(data.at(i).at(j)-1)+=1;
    }
  }
  for(int i=0;i<N;i++){
    cout<<ans.at(i)<<endl;
  }
}

Measured memory_bytes: 3612
n,t = map(int,input().split())
a = list(map(int,input().split()))
dif = []*n
for i in range(len(a)-1):
    dif.append(a[i+1]-a[i])

stan = [j for j in dif if j >= t]
suf = [k for k in dif if k < t]
print(sum(suf) + (t)*(len(stan)+1))

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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

struct UF {
	vector <int> fa;
	UF(int n) { fa.resize(n); rep(i, n) fa[i] = i; }
	int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
	void merge(int x, int y) { fa[find(x)] = find(y); }
};

int h, w, k;
int sx, sy, ex, ey;
char temp[1 << 20];
vector <string> M;
vector <vector <int> > dis, rhv, chv;
vector <UF> ruf, cuf;
int que[1 << 21], ql, qr;

void ins(int x, int y, int d) {
	dis[x][y] = d;
	ruf[x].merge(y, y + 1);
	cuf[y].merge(x, x + 1);
	que[qr ++] = x, que[qr ++] = y;
}

int main() {
	scanf("%d %d %d", &h, &w, &k);
	scanf("%d %d %d %d", &sx, &sy, &ex, &ey), -- sx, -- sy, -- ex, -- ey;
	rep(i, h) scanf("%s", temp), M.pb(temp);
	rep(i, h) dis.pb(vector <int> (w, -1));
	rep(i, h) rhv.pb(vector <int> (w, 0)), ruf.pb(UF(w + 1));
	rep(i, w) chv.pb(vector <int> (h, 0)), cuf.pb(UF(h + 1));
	rep(i, h) rep(j, w) if (M[i][j] == '@') rhv[i][j] ++, chv[j][i] ++;
	rep(i, h) rep(j, w) if (j) rhv[i][j] += rhv[i][j - 1];
	rep(i, w) rep(j, h) if (j) chv[i][j] += chv[i][j - 1];
	ins(sx, sy, 0);
	while (ql < qr) {
		int x = que[ql ++], y = que[ql ++], d = dis[x][y];
		{ // row
			int ly = max(0, y - k);
			int uy = min(w - 1, y + k);
			ly = lower_bound(rhv[x].begin() + ly, rhv[x].begin() + y, rhv[x][y]) - rhv[x].begin(); if (M[x][ly] == '@') ++ ly;
			uy = upper_bound(rhv[x].begin() + y + 1, rhv[x].begin() + uy + 1, rhv[x][y]) - rhv[x].begin() - 1;
			for (int ny = ruf[x].find(ly); ny <= uy; ny = ruf[x].find(ny)) ins(x, ny, d + 1);
		}
		{ // col
			int lx = max(0, x - k);
			int ux = min(h - 1, x + k);
			lx = lower_bound(chv[y].begin() + lx, chv[y].begin() + x, chv[y][x]) - chv[y].begin(); if (M[lx][y] == '@') ++ lx;
			ux = upper_bound(chv[y].begin() + x + 1, chv[y].begin() + ux + 1, chv[y][x]) - chv[y].begin() - 1;
			for (int nx = cuf[y].find(lx); nx <= ux; nx = cuf[y].find(nx)) ins(nx, y, d + 1);
		}
	}
	printf("%d\n", dis[ex][ey]);
	return 0;
}


Measured memory_bytes: 130888
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
using namespace std;
typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
const int INF = 1001001001;
const ll LINF = 1e18;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const P p1, const P p2){ return p1.first < p2.first;};
bool p_comp_fg(const P p1, const P p2){ return p1.first > p2.first;};
bool p_comp_ss(const P p1, const P p2){ return p1.second < p2.second;};
bool p_comp_sg(const P p1, const P p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    string S; cin >> S;
    auto yy = S.substr(0,4);
    auto mm = S.substr(5,2);
    auto dd = S.substr(8,2);
    if(yy <= "2019" && mm <= "04" && dd <= "30") cout << "Heisei" << endstr;
    else cout << "TBD" << endstr;
    return 0;
}


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

using namespace std;

//#define int long long
#define FOR(i, j, k) for(int i = j; i < (int)k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF (1 << 30)

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;

const int MOD = 1e9 + 7;
const int dy[] = {0, 0, 1, -1};
const int dx[] = {1, -1, 0, 0};

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

string s[100];
bool went[100][100];
int h, w, cnt;

void dfs(int y, int x, char t) {
    if(went[y][x]) return;
    went[y][x] = true;
    ++cnt;
    rep(i, 4) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
        if(s[ny][nx] == t) {
            dfs(ny, nx, t);
        }
    }
}

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

    while((cin >> h >> w), h | w) {
        rep(i, h) cin >> s[i];
        int res = 0;
        cnt = 0;
        memset(went, 0, sizeof(went));
        rep(i, h) rep(j, w) {
            cnt = 0;
            dfs(i, j, s[i][j]);
            if(cnt > 0) ++res;
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 4056
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(ALL(a));

    if(a[n-1] - a[0] > 1){
        cout << "No" << endl;
        return 0;
    }

    if(a[0] == n - 1 && a[0] == a[n-1]){
        cout << "Yes" << endl;
        return 0;
    }

    int m = a[n-1];
    int cnt = 0;
    rep(i, n){
        if(a[i] != m){
            cnt++;
        }
    }

    int mini = 0;
    if(n / m == 1){
        mini = m - n % m;
    }
    int maxi = m - 1;

    if(mini <= cnt && cnt <= maxi){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    string s;
    cin>>s;
    for(int i=0;i<5;i++)cout<<s[i];
    cout<<" ";
    for(int i=6;i<13;i++)cout<<s[i];
    cout<<" ";
    for(int i=14;i<19;i++)cout<<s[i];
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3624
/**
 * @author torith
 * @date 2018-10-10
 */

#include <bits/stdc++.h>

using namespace std;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int K;
    cin >> K;

    // substringの列挙
    vector<string> S;
    for (int i = min(K,int(s.size())); i > 0; --i) {
        int j = 0;
        while(j + i <= s.size()){
            S.push_back(s.substr(j, i));
            j++;
        }
    }

    // ソート＆重複削除
    sort(S.begin(),S.end());
    unique(S.begin(),S.end());

    cout << S[K-1] << "\n";

    return 0;
}



Measured memory_bytes: 1660
// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);
//#define _GLIBCXX_DEBUG//only for debugging
/*BISMILLAH UR RAHMAN*/ 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define debug(x) std::cerr << #x << ": " << (x) << '\n';
#define sz(x) int(x.size())
#define INF INT_MAX;
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> ii;
int arr[int(1e5+10)];
int dp[int(1e5+10)];
int main()
{  
  fast
  int n;
  cin>>n;
  for(int i=1;i<=n;++i)cin>>arr[i];
  dp[1]=0;dp[2]=abs(arr[2]-arr[1]);
  for(int i=3;i<=n;++i)
  {
    dp[i]=min(abs(arr[i]-arr[i-2])+dp[i-2],abs(arr[i]-arr[i-1])+dp[i-1]);

  }
 cout<<dp[n]<<endl;
  
  

}

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

int main() {
  int h1, m1, h2, m2, k;
  scanf("%d%d%d%d%d", &h1,&m1,&h2,&m2,&k);
  int t=h2*60+m2 - h1*60-m1;
  printf("%d", t-k);
  return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll ceil(ll x,ll y){
	if(x % y == 0) return x / y;
	return x / y + 1;
}

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

	ll k;
	cin >> k;

	ll a[k];
	rep(i,k) cin >> a[i];

	ll l,r;
	l = r = 2;

	rep(i,k){
		ll b = a[k-1-i];
		l = ceil(l,b) * b;
		r = r / b * b + b - 1;
	}

	if(r < l) cout << -1 << endl;
	else cout << l << " " << r << endl;
}

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

int main(){
    ll a;
    long double b;
    
    cin >> a >> b;
    /*double syousuu = b-ll(b);
    ll syousuuseki = syousuu*a;
    cout << a*ll(b)+syousuuseki << endl;*/
    cout << ll(a*b) << endl;
}

Measured memory_bytes: 3732
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

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

const int INF = 1e9;
const int MOD = 1e9+7;

const double EPS = 1e-9;

bool check(double vix, vector<pair<double, double> > ob, double d){
    for(int i = 0; i < ob.size(); i++){
        double x = ob[i].first;
        double y = ob[i].second;
        while(x > d) x -= d;
        double viy = d / vix / 2;
        double by = -1 * x * x / (2* vix * vix) + viy * x / vix;
        if(by < y - EPS) return true;
    }
    return false;
}

int main(void){
    double d, n, b;
    cin >> d >> n >> b;
    vector<pair<double, double> > ob(n);
	REP(i, n) cin >> ob[i].first >> ob[i].second;
    double ans = 1e9;
    for(int i = 1; i <= b+1; i++){
        double fd = d / i;
        double left = 0.0, right = 1e5;
        while(right - left > EPS){
            double med = (right + left) / 2;
            int f = 0;
            if(check(med, ob, fd)) f = 1;
            if(f) right = med;
            else left = med;
        }
        //cout << "result : " << right << endl;
        left = 0.0;
        while(right - left > EPS){
            double med1 = (right - left) / 3 + left;
            double med2 = (right - left) *2 / 3 + left;
            double y = fd / med1 / 2;
            double ret1 = sqrt(med1 * med1 + y * y);
            y = fd / med2 / 2;
            double ret2 = sqrt(med2 * med2 + y * y);
            if(ret1 > ret2){
                left = med1;
            }
            else right = med2;
            //cout << "left : right " << left << ":" << right << endl;
        }
        double y = fd / right / 2;
        ans = min(ans, sqrt(right * right + y * y));
    }
    printf("%.9f\n", ans);
    return 0;
}

Measured memory_bytes: 1248
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#ifndef debug_on
#define debug_on 0
#endif

#define dbg \
    if(debug_on) cerr << "DEBUG:"
#define ast(cond)           \
    do {                    \
        if((cond) == false) \
        {                   \
            if(debug_on)    \
            cerr << "ASSERT" << #cond " failed at line:" << __LINE__ << endl;   \
            exit(1);        \
        }                   \
    }while(0)

int UpDiv(int a, int b)
{
    return (a + b - 1) / b;
}

int main(int, char *[])
{
    int N, K;
    int i_loc = 0;
    cin >> N >> K;
    for(int i = 0; i < N; ++i)
    {
        int v;
        cin >> v;
        if(v == 1)
            i_loc = i;
    }

    int min_count = 0;
    if(N <= K)
        min_count = 1;
    else
    {
        if(i_loc >= N/2)
            i_loc = N - 1 - i_loc;
        
            min_count = UpDiv(N - K, K - 1) + 1;
#if 0
        //always front half
        if(i_loc < K)
        {
            min_count = UpDiv(N - K, K - 1) + 1;
        }
        else
        {
            ++min_count;
            min_count += UpDiv(i_loc - K + 1, K - 1);
            min_count += UpDiv(N - 1 - i_loc, K - 1);
        }
#endif
    }

    cout << min_count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <sstream>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}


int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    rep (i,h){
        cin >> s[i];
    }

    rep(i,h){
        rep(j,w){
            if (s[i][j] == '.'){
                int cnt = 0;
                for (int m=-1;m<2;m++){
                    for (int l=-1;l<2;l++){
                        if ( 0<=(i+m)&&(i+m)<h && 0<=(j+l)&&(j+l)<w && s[i+m][j+l]=='#'){
                            cnt+=1;
                        }
                    }
                }
                string ans = to_string(cnt);
                cout << ans;
                // s[i].replace(1,j,ans);
            }
            else cout << s[i][j];
        }
        cout << endl;
    }

    // rep(i,h){
    //     cout << s[i] << endl;
    // }


    return 0;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mod 1000000007
int main()
{
    fast;
    ll n,W;
    cin>>n>>W;
    ll a[n+2][2];
    for(int i=0;i<n;i++)
    {
        cin>>a[i][0]>>a[i][1];
    }
    vector<ll> dp(W+1,0);
    //a[i][0] -> wt
    //a[i][1] -> val
    vector<ll> ndp(W+1,0);
    for(int i=0;i<n;i++)
    {
        
        for(int j=W-a[i][0];j>=0;j--)
        {
            {
                dp[j+a[i][0]]=max(a[i][1] + dp[j] , dp[j+a[i][0]]);
            }
        }
        
        // dp=ndp;
    }
    // for(int j:dp)cout<<j<<" ";cout<<"\n";
    cout<<dp[W];
return 0;
}

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

int main(){
	int size;
	int a, z;
	string s;
	cin >> s;
	
	a=s.find("A");
	z=s.rfind("Z");
	
	cout << (z-a+1) << endl;
	
	return 0;
}

Measured memory_bytes: 640
#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 = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;




signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n; cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  
  vsort(a);
  
  set<ll> s;
  set<ll> res;
  map<ll,ll> same;
  ll ans=0;
  rep(i,n){
    same[a[i]]++;
    if(same[a[i]]>1) continue;
    
    vector< ll > ret;
    for(ll j = 1; j * j <= a[i]; j++) {
      if(a[i] % j == 0) {
        ret.push_back(j);
        if(j*j != a[i]) ret.push_back(a[i] / j);
      }
    }
    
    bool ok=true;
    for(auto e: ret){
      if(s.count(e)){
        ok=false;
        break;
      }
      // cout<<e<<' ';
    }
    // cout<<endl;
    if(ok){
      ans++;
      res.insert(a[i]);
    }
    s.insert(a[i]);
  }
  
  for(auto e: same){
    if(res.count(e.first) && e.second>1) ans--;
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 35908
#include<iostream>
#include<algorithm>
#define FOR(i,e) for(int i=0;i<(int)(e);i++)
using namespace std;

int main(){
  double pb[100][5001];
  int x,y,z;
  int v[4],e[51],a[51];

  while(cin >> x >> y >> z && (x||y||z)){

    FOR(i,x)cin >> v[i];
    FOR(i,y+1)e[i] = a[i] = 0;
    FOR(i,z){
      int n,m,l;
      cin >> n >> m >> l;
      e[n] = m; a[n] = l;
    }

    FOR(i,y+1)FOR(j,5001)pb[i][j] = 0.0;
    pb[0][0] = 1.0;

    FOR(i,y)FOR(j,5001){
      FOR(k,x){
	if(pb[i][j] == 0.0)continue;
	int next = min(y,i+v[k]),value = j;
	if(e[next] == 1)next = min(y,next+a[next]);
	else if(e[next] == 2)value = j + a[next];
	else if(e[next] == 3)value = max(0,j-a[next]);
	pb[next][value] += pb[i][j]/x;
      }
    }

    double ans = 0.0;
    FOR(i,5001)ans += pb[y][i] * i;
    cout << (int)(ans) << endl;
  }
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
   string s;cin >>s;
   vector<int>direction(4,-1);
   char x[4]={'N','S','W','E'};
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < 4; ++j) {
            if(s[i]==x[j]){
                direction[j]+=2;
            }
        }
    }
    if(direction[0]*direction[1]<0||direction[2]*direction[3]<0){
        puts("No");
    }
    else {
        puts("Yes");
    }
   return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, lim, v, w;
  cin >> n >> lim;
  int dp[110][10010], weight[110],value[110];
  for(int i = 0; i < n; i++) cin >> value[i] >> weight[i];
  for(int i = 0; i < lim; i++) dp[0][i] = 0;
  for(int i = 0; i < n; i++){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < lim + 1; j++){
        if(j >= weight[i]){
          dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j]);
        }
        else dp[i + 1][j] = dp[i][j];
      }
    }
  }
  cout << dp[n][lim] << endl;
}


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

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

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

vector<int> divisor(int n) {
  vector<int> ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ALL(ret));
  return ret;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, int> mp;
  REP(i,n){ 
    cin >> a[i];
    mp[a[i]]++;
  }

  int ans = n;
  REP(i,n){
    mp[a[i]]--;

    auto div = divisor(a[i]);
    for(auto d: div){
      if(mp[d]>0){
        ans--;
        break;
      }
    }

    mp[a[i]]++;
  }

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 33036
#include <stdio.h>
#include <algorithm>
int a, b;
int main() {
	while(scanf("%d%d", &a, &b), a + b) {
		int ret = 999999999;
		for(int i = 1; i * i <= a; i++) {
			if(a % i) continue;
			for(int j = 1; j * j <= b; j++) {
				if(b % j) continue;
				int p[4] = { i, a / i, j, b / j };
				std::sort(p, p + 4);
				int res = 0;
				for(int k = 0; k < 3; k++) res += (p[k + 1] - p[k]) * (p[k + 1] - p[k]);
				ret = std::min(ret, res);
			}
		}
		printf("%d\n", ret);
	}
}

Measured memory_bytes: 2732
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
#include <stack>
/*多倍長整数/cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
*/

//#pragma gcc target ("avx2")
//#pragma gcc optimization ("o3")
//#pragma gcc optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a) //少数出力
#define printLdb(a) printf("%.50Lf\n", a) //少数出力
#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str()) //string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2.0) //等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)
#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)
#define Please return
#define AC 0
#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acosl(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1 && c != ' ') {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n;
	scanf("%d", &n);
	vector<int> a(n);
	rep(i, n)scanf("%d", &a[i]);
	sort(all(a));
	a.erase(unique(all(a)), a.end());
	printf("%d\n", (int)a.size() - !(a.size() % 2));

	Please AC;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#define endl '\n'
#define ll long long
#define mod 10007
#define NCONS 200001
//#define NCONS 100001
//#define NCONS 1001
//#define NCONS 10
#define MCONS 2001
#define LIMIT 1000000000
#define TRUE 1
#define FALSE 0

using namespace std;

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int a, b; cin >> a >> b;
    int big = max(a, b);
    int small = min(a, b);
    cout << max(big + big - 1, big + small) << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    char s;
    cin >> s;
    int ch = s;
    if (isupper(ch))
        cout << "A" << endl;

    if (islower(ch))
        cout << "a" << endl;
    return 0;
}

Measured memory_bytes: 3624
import itertools
n = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
tmp = list(itertools.permutations(range(1,n+1)))
tmp = sorted(tmp)
for index,t in enumerate(tmp):
  if list(t) == P and list(t) == Q:
    p = index+1
    q = index+1
  elif list(t) == P:
    p = index+1
  elif list(t) == Q :
    q = index+1
  
print(abs(p-q))

Measured memory_bytes: 80172
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_N, MAX_V = 100, 100


def solve():
    dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(MAX_N * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[c_items][i] <= real_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

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

int main()
{
    int cnt=0,ans=0;
    string c;
    cin>>c;
    for(int i=0;i<c.size();i++){
    if(c[i]=='A') cnt++;
    else if(c[i]=='T') cnt++;
    else if(c[i]=='C') cnt++;
    else if(c[i]=='G') cnt++;
    else {
        ans= ans>cnt ? ans : cnt;
        cnt=0;
    }
    if(i+1==c.size()){
         ans= ans>cnt ? ans : cnt;
        cnt=0;
    }
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<int> dp(n + 1, INF);
    for(int i = 0; i < n; i++){
        *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << endl;
}


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

#define INF 1010001000
#define EPS 1e-10
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef pair<int, int> i_i;
typedef long long int llong;
typedef pair<llong, llong> ll_ll;
typedef struct edge {int f, t;}Edge;

void dij(int st, int en);

vector<vector<int> > edge(101, vector<int>(101, INF));
vector<vector<bool> > used(101, vector<bool>(101, false));
int n, m;

int main()
{
    cin >> n >> m;
    int ret = 0;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        if (edge[a][b] == INF) {
            edge[a][b] = c;
            edge[b][a] = c;
        } else {
            ret++;
            edge[a][b] = min(edge[a][b], c);
            edge[b][a] = min(edge[b][a], c);
        }
    }
    rep(i, n) {
        for (int j = i+1; j < n; j++) {
            dij(i+1, j+1);
        }
    }
    rep(i, n) {
        for (int j = i+1; j < n; j++) {
            if (edge[i+1][j+1] != INF && !used[i+1][j+1]) {
                ret++;
            }
        }
    }
    cout << ret << endl;
    return 0;
}

void dij(int st, int en)
{
    vector<int> ans(101, INF);
    vector<int> prev(101, 0);
    priority_queue<i_i, vector<i_i >, greater<i_i > > pq;
    pq.push(i_i(0, st));
    ans[st] = 0;
    while (!pq.empty()) {
        i_i p = pq.top(); pq.pop();
        int u = p.second;
        if (ans[u] < p.first) {
            continue;
        }
        rep(i, n) {
            if (ans[i+1] > ans[u] + edge[u][i+1]) {
                ans[i+1] = ans[u] + edge[u][i+1];
                pq.push(i_i(ans[i+1], i+1));
                prev[i+1] = u;
            }
        }
    }
    int next = en;
    while (1) {
        if (next == st) {
            break;
        } else {
            used[prev[next]][next] = true;
            used[next][prev[next]] = true;
            next = prev[next];
        }
    }
}



Measured memory_bytes: 256
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

import random


def main():
    n = int(input())
    v = list(map(int, input().split()))
    v.sort()                    # increasing way
    # eprint(v)

    sum=0
    sum+=v[0]+v[1]
    
    for i in range(2,n):        # i is index of the ingredients.
        coef = i-1
        # eprint("coef "+str(coef))
        sum += pow(2,coef) * v[i]
        # eprint("sum "+str(sum))

    print(sum/pow(2,n-1))
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 66412
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,c;
    cin>>n>>m>>c;
    int cnt = 0;
    int b[m];
    int a[n][m];
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        int sum =0;
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            sum += a[i][j] * b[j];
        }
        if(sum+c > 0) cnt++;
    }
    
    cout<< cnt <<endl;
}


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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;
    
    VI a(n);
    FOR(i,0,n-1) {
        cin >> a[i]; a[i]--;
    }
    
    VL add(2*m+2,0), rem(2*m+2,0);
    
    FOR(i,0,n-2) if (a[i+1] != a[i] && a[i+1] != a[i] + 1) {
        int l = a[i], r = a[i+1];
        
        if (r < l) {
            r += m;
        }
        
        add[l+2]++;
        add[r+1]--;
        
        rem[r+1] += r - l - 1;
    }
    
    FOR(i,1,2*m+1) {
        add[i] += add[i-1];
    }
    
    FOR(i,m,2*m+1) {
        add[i % m] += add[i];
        rem[i % m] += rem[i];
    }
    
    ll currScore = 0, bestScore = -INF;
    int best = -1;
    
    FOR(i,0,m-1) {
        currScore += add[i];
        currScore -= rem[i];
        
        if (currScore > bestScore) {
            bestScore = currScore;
            best = i;
        }
    }
    
    ll ans = 0;
    FOR(i,0,n-2) if (a[i] != a[i+1]) {
        int l = a[i], r = a[i+1];
        
        if (r < l) {
            r += m;
        }
        
        int here = r - l;
        
        if (best >= l && best <= r) {
            here = min(here, r - best + 1);
        }
        
        if (best + m <= r) {
            here = min(here, r - (best + m) + 1);
        }
        
        ans += here;
    }
    
    cout << ans;

    return 0;
}

/*************************************************************************/


Measured memory_bytes: 3840
N = int(input())
cnt = 0
i = 10
dp = [0,1,2,3,4,5,1,2,3,1]
while i<=N:
    idx_n,idx_s = 0,0
    while i-(9**idx_n)>=0:
        idx_n += 1
    idx_n -= 1
    while i-(6**idx_s)>=0:
        idx_s += 1
    idx_s -= 1
    dp.append(min(1+dp[i-(9**idx_n)],1+dp[i-(6**idx_s)]))
    i += 1
print(dp[N])


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

int main() {
  int souKyori;
  int house;
  int idoKyori = 0;
  int maxKyori_R;
  int maxHouse_R;
  int maxKyori_L;
  int maxHouse_L;
  cin >> souKyori >>house;
  
  vector<int> vec(house);
  for(int i = 0; i < house; i++){
   cin >> vec.at(i);
  }
  
  // 一番離れている家をサーチ(右回り)
  for(int i = 0; i < house; i++){
    int tmp;
    if(i == house-1){
      tmp = (souKyori - vec.at(house-1)) + vec.at(0);
    }else{
      tmp = vec.at(i+1) - vec.at(i); 
    }
    
    if( maxKyori_R < tmp){
      maxKyori_R = tmp;
      maxHouse_R = i;
    }
    
    idoKyori += tmp;
  }
  
  idoKyori -= maxKyori_R;

  cout << idoKyori << endl;
}



Measured memory_bytes: 1024
#include<iostream>
using namespace std;
string s;
long cnt[2019];

int main() {
	cin>>s;
	int now=0;
	long ans=0,p=1,pi=1;
	cnt[0]=1;
	for(int i=s.size();i--;)
	{
		now=(now+(s[i]-'0')*p)%2019;
		ans+=cnt[now]++;
		p=p*10%2019;
	}
	cout<<ans<<endl;
}

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

int main(){
	int n;
	cin>>n;
	int x=n%10;
	
	if(x==2|| x==4 || x==5 || x==7 || x==9)
		cout<<"hon"<<endl;
	else if(x==0 || x==6 || x==1 || x==8)
		cout<<"pon"<<endl;
	else
		cout<<"bon"<<endl;
		
	return 0;
}

Measured memory_bytes: 3592
import java.util.*;
import java.io.*;

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

        char[] str = in.nextLine().toCharArray();

        for(int i = 0; i < str.length; i++){
            if(str[i] >= 65 && str[i] <= 90) str[i] += 32;
            else if(str[i] >= 97 && str[i] <= 122)str[i] -= 32;

            System.out.print(str[i]);
        }
        System.out.println();

    }
}


Measured memory_bytes: 26884
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main() {
    int n;
    scanf("%d", &n);
   // dp[heads]
    // if we had i tosses, then tails=i-heads
    vector<double> dp(n + 1);
    // dp[i] - p-bility that there are i heads so far
    dp[0] = 1;
    for(int coin = 0; coin < n; ++coin) {
        double p_heads;
        scanf("%lf", &p_heads);
        for(int i = coin + 1; i >= 0; --i) {
            dp[i] = (i == 0 ? 0 : dp[i-1] * p_heads) + dp[i] * (1 - p_heads);
        }
    }
    double answer = 0;
    for(int heads = 0; heads <= n; ++heads) {
        int tails = n - heads;
        if(heads > tails) {
            answer += dp[heads];
        }
    }
    printf("%.10lf\n", answer);
}

Measured memory_bytes: 384