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

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef long double ld;

const ll LLINF = (ll) 1e18;

vector<tuple<ll, ll, ll>> g[50];
ll dp[50][5000];
pair<ll, ll> ex[50];

struct pp {
	ll v, have, time;

	pp(ll a, ll b, ll c) {
		v = a;
		have = b;
		time = c;
	}
};

bool operator<(const pp &a, const pp &b) {
	return a.time > b.time;
}

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

#ifdef LOCAL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	auto START = chrono::steady_clock::now();
#endif

	int nv, ne, s;
	cin >> nv >> ne >> s;

	for (int i = 0; i < ne; i++) {
		ll u, v, cost, t;
		cin >> u >> v >> cost >> t;

		--u;
		--v;
		g[v].emplace_back(u, cost, t);
		g[u].emplace_back(v, cost, t);
	}

	for (int i = 0; i < nv; i++) {
		cin >> ex[i].first >> ex[i].second;
		g[i].emplace_back(i, -ex[i].first, ex[i].second);
	}

	for (auto & i : dp) {
		for (long long & j : i) {
			j = LLINF;
		}
	}

	priority_queue<pp> pq;
	pq.emplace(0, s, 0);
	dp[0][min(s, 4999)] = 0;

	while (!pq.empty()) {
		pp v = pq.top();
		pq.pop();

		for (auto e : g[v.v]) {
			ll toV = get<0>(e);
			ll need = get<1>(e);
			ll goTime = get<2>(e) + v.time;

			if (need <= v.have) {
				ll nextHave = v.have - need;
				nextHave = min(nextHave, 4999LL);

				if (dp[toV][nextHave] > goTime) {
					dp[toV][nextHave] = goTime;
					pq.emplace(toV, nextHave, goTime);
				}
			}
		}
	}

	for (int i = 1; i < nv; i++) {
		ll res = LLINF;

		for (int j = 0; j < 5000; j++) {
			res = min(res, dp[i][j]);
		}

		cout << res << "\n";
	}

#ifdef LOCAL
	cerr << "Working time: " << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - START).count()
			 << " ms.";
#endif

	return 0;
}

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = LLONG_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	ll n, a;

	cin >> n;

	multiset<ll> s;
	ll ans = 1;

	cin >> a;
	s.insert(a);

	FOR(i, 1, n) {
		cin >> a;
		auto it = s.begin();
		if (a <= *it) {
			ans++;
			s.insert(a);
		}
		else {
			auto itr = s.lower_bound(a);
			itr--;
			s.erase(itr);
			s.insert(a);
		}
	}

	cout << ans << endl;
}

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

int main(){

  int N, M, P;

  while(cin >> N >> M >> P && (N || M || P)){

    int sum = 0;
    int maisu = 0, win = -1;
    

    for(int i = 1; i <= N; i++){
      cin >> maisu;
      sum += maisu;
      if(i == M) win = maisu;
    }
    if(win == 0) cout << 0 << endl;
    else    cout << ((sum * 100 * (100 - P)) / 100) / win << endl;
    win = -1;
    maisu = 0;
    sum = 0;
  }

  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(X) ((int)(X).size())
#define endl "\n";
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
  	int n,k,a[51],ans=0;
  	cin>>n>>k;
  	for (int i = 0; i < n; ++i)
  		{
  			cin>>a[i];
  		}	
     sort(a,a+n);
     for (int i = n-k; i < n; ++i)
     {
     	ans+=a[i];
     }
     cout<<ans;
   return 0;
}


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main() {
	int a, b, c;
	int k = 3;
	cin >> a >> b >> c;
	if (a - b == 0)k--;
	if (b - c == 0)k--;
	if (c - a == 0)k--;
	if (k == 0)k = 1;
	cout << k << endl;
	return 0;
}

Measured memory_bytes: 256
import math

n, k = map(int, input().strip().split())


prob = 0
for m in range(1, n + 1):
    if m >= k:
        prob += 1 / n
    else:
        p = math.ceil(math.log(k / m) / math.log(2))
        prob += (1 / n) / (2 ** p)

print(prob)


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

int main(){
    int n;
    cin >> n;
    double arr[n];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    sort(arr, arr+n);
    double cntr = (arr[0] + arr[1]) / 2;
    for(int i=2; i<n; i++){
        cntr = (cntr+arr[i])/2;
    }
    cout << cntr;
    return 0;
}

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

using namespace std;
typedef long long ll;
bool valid(vector<ll> &A, vector<ll> &F, ll mid, ll K) {
 for (int i = 0; i < A.size(); i++) {
  ll max_A = mid / F[i];
  K -= max(0LL, A[i] - max_A);
  if (K < 0) {
   return false;
  }
 }
 return true;
}

int main()
{
 ll N, K;
 cin >> N >> K;
 vector<ll> A(N);
 vector<ll> F(N);
 for (int i = 0; i < N; i++) {
  cin >> A[i];
 }
 for (int i = 0; i < N; i++) {
  cin >> F[i];
 }
 sort(A.begin(), A.end());
 sort(F.rbegin(), F.rend());
 ll lo = 0, hi = 1e12, res;
 while (lo <= hi) {
  ll mid = lo + (hi - lo) / 2;
  if (valid(A, F, mid, K)) {
   res = mid;
   hi = mid - 1;
  } else {
   lo = mid + 1;
  }
 }
 cout << res << endl;
 return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int s,t,d;
ll w[100001];
ll sum=0;
ll af[100001];

int main(void){
	scanf("%d%d%d",&s,&t,&d);
	for(int i=0;i<d;i++){
		scanf("%lld",&w[i]);
		sum-=w[i];
	}
	ll res=-2;
	ll now=s;
	for(int i=0;i<d;i++){
		now+=w[i];
		if(now<=t){
			printf("%d\n",i+1);
			return 0;
		}else if(sum>0LL){
			ll rest=now-t;
			ll val=(ll)i+(rest+sum-1LL)/sum*d;
			if(res==-2){
				res=val;
			}else{
				res=min(res,val);
			}
		}
	}
	printf("%lld\n",res+1LL);
	return 0;
}

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

int main(){
	stack<int> S;
	string word;

	while(cin >> word){	//??\???????????????????¶???????
		if(word == "+"){
			int i = S.top();
			S.pop();
			int j = S.top();
			S.pop();
			S.push(j+i);
		}else if(word == "-"){
			int i = S.top();
			S.pop();
			int j = S.top();
			S.pop();
			S.push(j-i);
		}else if(word == "*"){
			int i = S.top();
			S.pop();
			int j = S.top();
			S.pop();
			S.push(j*i);
		}
		else{
			int num = stoi(word);
			S.push(num);
		}
	}

	int ans = S.top();
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <string>
using namespace std;
int main(){
    string S,result;
    cin >> S;
    for(int index=0; index < S.length(); index++){
        if(S[index]=='B'){
            if(result.length()!=0){
                result.erase(result.length()-1);
            }
        }else{
            result+=S[index];
        }
    }
    cout << result << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define inf (int)1e8
using namespace std;

int n, m, r;
int dis[205][205][2] = {0}, dp[1005][205];
vector<int> z;

int solve();

int main() {
  while(1) {
    cin >> n >> m;
    if(n + m == 0) break;
    for(int t = 0; t < 2; ++t)
      for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) dis[i][j][t] = inf;
    for(int t = 0; t < 2; ++t)
      for(int i = 0; i < n; ++i) dis[i][i][t] = 0;
    for(int i = 0; i < m; ++i) {
      int x, y, t;
      string s;
      cin >> x >> y >> t >> s;
      --x, --y;
      dis[x][y][s == "L"] = min(dis[x][y][s == "L"], t);
      dis[y][x][s == "L"] = min(dis[y][x][s == "L"], t);
    }
    cin >> r;
    z.resize(r);
    for(int i = 0; i < r; ++i) {
      cin >> z[i];
      --z[i];
    }
    cout << solve() << endl;
  }
  return 0;
}

int solve() {
  if(r == 1) return 0;
  int ans = inf;
  // WF
  for(int t = 0; t < 2; ++t)
    for(int k = 0; k < n; ++k)
      for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
          dis[i][j][t] = min(dis[i][j][t],
                             dis[i][k][t] + dis[k][j][t]);
  for(int i = 0; i < r; ++i)
    for(int j = 0; j < n; ++j) dp[i][j] = inf;
  for(int i = 0; i < n; ++i) dp[0][i] = dis[z[0]][i][0];
  for(int i = 1; i < r; ++i)
    for(int j = 0; j < n; ++j) {
      dp[i][j] = min(dp[i][j],
                     dp[i - 1][j] + dis[z[i - 1]][z[i]][1]);
      for(int k = 0; k < n; ++k) {
        dp[i][j] = min(dp[i][j],
                       dp[i - 1][k] + dis[z[i - 1]][k][1] +
                           dis[k][j][0] + dis[j][z[i]][1]);
        if(i == r - 1) ans = min(ans, dp[i][j]);
      }
    }
  return ans;
}


Measured memory_bytes: 4272
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,count=0;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    if(i%2==1)
    {
      count++;
    }
  }
  double div = (double)count/n;
  cout<<fixed<<setprecision(10)<<div<<endl;
  
  return 0;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
a=[]
used=[[False for _ in range(w)] for _ in range(h)]
ans=[]
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        if(ai[j]%2!=0):
            if(j<w-1 and ai[j]>0 and ai[j]%2!=0 and not used[i][j]):
                used[i][j]=True
                ai[j]-=1
                ai[j+1]+=1
                ans.append([i+1,j+1,i+1,j+2])
    a.append(ai)

for i in range(h):
    if(i<h-1 and a[i][w-1]>0 and a[i][w-1]%2!=0 and not used[i][w-1]):
        used[i][w-1]=True
        a[i][w-1]-=1
        a[i+1][w-1]+=1
        ans.append([i+1,w,i+2,w])

print(len(ans))
for i in range(len(ans)):
    print(*ans[i])


Measured memory_bytes: 32380
#include <cstdio>
#include <cmath>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

typedef double D;
const D EPS = 1e-8;
const D INF = 1e10;
const D PI = M_PI;

struct P {
    D x, y;
    P(D xs, D ys) : x(xs), y(ys) { }
    P() { }
};
P operator +(P a, P b) { return P(a.x + b.x, a.y + b.y); }
P operator -(P a, P b) { return P(a.x - b.x, a.y - b.y); }
P operator *(P p, D s) { return P(p.x * s, p.y * s); }

D inp(P a, P b) { return a.x*b.x + a.y*b.y; }
D outp(P a, P b) { return a.x*b.y - a.y*b.x; }
D norm(P p) { return inp(p, p); }
D abs(P p) { return sqrt(norm(p)); }
bool eq(P a, P b) { return abs(a - b) < EPS; }
D arg(P p) { return atan2(p.y, p.x); }
P rot90(P p) {
    return P(-p.y, p.x);
}
P rot(P p, D radian) {
    P q;
    q.x = cos(radian)*p.x - sin(radian)*p.y;
    q.y = sin(radian)*p.x + cos(radian)*p.y;
    return q;
}
struct L : vector<P> {
    P a, b;
    L(P as, P bs) : a(as), b(bs) { }
};
P projection(L l, P p) { // ??卒???l???????????????p?????????
    P a = l.b - l.a;
    P b = p - l.a;
    D t = inp(b, a) / norm(a);
    return l.a + a * t;
}
P reflection(L l, P p) { // ??卒???l???????????????p???????属?
    return p + (projection(l, p) - p) * 2;
}
int ccw(P a, P b, P c) {
    b = b - a; c = c - a;

    // a - b - c ????????????????????即???
    if(outp(b, c) > EPS)  return +1; // ???????即???????
    if(outp(b, c) < -EPS) return -1; // ????即???????

    // a - b - c ?????卒??????????????其??即???
    if(inp(b, c) < 0)     return +2; // c - a - b
    if(norm(b) < norm(c)) return -2; // a - b - c
    return 0;                        // a - c - b
}
bool iSS(L s, L t) { // ????????????
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
        ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
bool iSP(L s, P p) {
    return ccw(s.a, s.b, p) == 0;
}
D dSP(L s, P p) {
    P r = projection(s, p);
    if(iSP(s, r)) return abs(r - p);
    return min(abs(s.a - p), abs(s.b - p));
}
D dSS(L s, L t) {
    if(iSS(s, t)) return 0;
    return min(min(dSP(s, t.a), dSP(s, t.b)),
            min(dSP(t, s.a), dSP(t, s.b)));
}
/* ?????????????????即??????iSS(s,t)????蔵???????????????即 */
P cLL(L l, L m) {
    D d = outp(m.b - m.a, l.b - l.a);
    return l.a + (l.b - l.a) * outp(m.b - m.a, m.b - l.a) * (1.0 / d);
}

typedef vector<P> Poly;
P at(const Poly &ps, int i) { return ps[i % ps.size()]; }
D polyArea(const Poly &ps) {
    D res = 0.0;
    for(int i = 0; i < (int)ps.size(); i++) {
        res += outp(at(ps, i), at(ps, i + 1));
    }
    return res / 2.0;
}
struct C {
    P p; D r;
    C(P ps, D rs) : p(ps), r(rs) { }
    C() { }
};

int main() {
    int N; scanf(" %d", &N);
    Poly ps(N);
    for(int i = 0; i < N; i++) {
        scanf(" %lf %lf", &ps[i].x, &ps[i].y);
    }
    printf("%.1f\n", polyArea(ps));
}

Measured memory_bytes: 1236
def abc177_e():
    n = int(input())
    A = [int(x) for x in input().split()]

    def prime_factorize(n:int)->set:
        ''' nの素因数分解 '''
        arr = []
        while n % 2 == 0:
            arr.append(2)
            n = n // 2
        f = 3
        while f*f <= n:
            if n%f == 0:
                arr.append(f)
                n = n // f
            else:
                f += 2
        if n != 1:
            arr.append(n)
        return set(arr)

    import math
    gcd_all = A[0]
    factors = [0]*(10**6 + 1)
    pairwise = True

    for ai in A:
        gcd_all = math.gcd(gcd_all, ai)
        for p in prime_factorize(ai):
            if factors[p]: pairwise = False
            factors[p] = 1

    if pairwise: ans = 'pairwise coprime'
    elif gcd_all == 1: ans = 'setwise coprime'
    else: ans = 'not coprime'
    print(ans)

if __name__ == '__main__':
    abc177_e()

Measured memory_bytes: 189552
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int a[100100], b[100100];
VVI edge(100100);

void bfs(int N){
    
    int done[N]; // 未訪問0, 既訪問1
    for(int i=0; i<N; i++) done[i] = 0;

    vector<map<int, int>> color(N);
    
    queue<int> que;
    queue<int> pre_node;
    queue<int> pre_color;
    
    int c=1;
    for(auto i : edge[0]){
        color[0][i] = c;
        que.push(i);
        pre_node.push(0);
        pre_color.push(c++);
    }
    done[0] = 1;
    
    while(!que.empty()){

        int node = que.front(); que.pop();
        int pn = pre_node.front(); pre_node.pop();
        int pc = pre_color.front(); pre_color.pop();

        if(done[node] == 1) continue;
        done[node] = 1;

        int c=1;
        for(int i : edge[node]){
            if(pn == i) continue;
            if(pc == c) c++;
            color[node][i] = c;

            que.push(i); pre_node.push(node); pre_color.push(c++);
        }
    }

    REP(i,N-1) cout << color[a[i]-1][b[i]-1] << endl;

    return;
}

int main(void){

    int N;
    cin >> N;
    REP(i,N-1) cin >> a[i] >> b[i];

    int d[N];
    REP(i,N) d[i] = 0;
    REP(i,N-1){
        d[a[i]-1]++; d[b[i]-1]++;
        edge[a[i]-1].push_back(b[i]-1);
        edge[b[i]-1].push_back(a[i]-1);
    }
    int K = 0;
    REP(i,N) chmax(K, d[i]);
    cout << K << endl;

    bfs(N);

    return 0;
}

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

int main(){
    string s;
    int i, j;
    bool flag = 0;
    long long cnt=0;
    long long res = 0;
    long long k, t, t1, t2;
    cin >> s >> k;
    
    if(s.length() == 1){
        cout << k/2 << endl;
        return 0;
    }

    flag = 0;
    for(int i=0; i<s.length(); i++){
        if(s[0] != s[i]) flag = 1;
    }
    if(flag == 0){
        if(s.length()%2 == 0){
            cout << (s.length()/2)*k << endl;
            return 0;
        }else{
            cout << s.length()*k/2 << endl;
            return 0;
        }
    }

    for(i=0; i<s.length(); i++){
        t = 0;
        for(j=i; s[i]==s[j] && j<s.length(); j++){
            t = j - i + 1;
            //cout << "t: " << t << endl;
        }
        cnt += t/2;
        //cout << cnt << endl;
        i = j-1;
    }
    res = cnt*k;
    if(s[0] == s[s.length()-1]){
        t1 = 0;
        for(i=0; s[0]==s[i] && i<s.length(); i++){
            t1 += 1;
        }
        //cout << "t1 " << t1 << endl;
        t2 = 0;
        for(i=0; s[s.length()-1]==s[s.length()-1-i] && i<s.length(); i++){
            t2 += 1;
        }
        //cout << "t2 " << t2 << endl;
        if(t1%2 == 1 && t2%2 == 1){
            res += k-1;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2, cos, pi
from fractions import Fraction

# t = int(stdin.readline())
# for _ in range(t):
# n, m = map(int, stdin.readline().split())
# nums = list(map(int, stdin.readline().split()))
# n = int(input())
# if n%10 in [2, 4, 5, 7, 9]:
#     print('hon')
# elif n%10 in [0, 1, 6, 8]:
#     print('pon')
# else:
#     print('bon')

# k = int(input())
# s = input()

# ans = s[:k] + ('...' if len(s) > k else '')
# print(ans)

hrhand, minhand, hr, minut = map(int, stdin.readline().split())

angmin =360*minut/60
anghr =360*(hr + minut/60)/12


totang = abs(angmin - anghr)


print((hrhand**2 + minhand**2 - 2*hrhand*minhand*cos(totang*pi/180))**0.5)



Measured memory_bytes: 77936
#include <iostream>
#include <set>

using namespace std;

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

	int number;
	set<int> numbers;
	for (int i = 0; i < n; i++) {
		cin >> number;
		numbers.insert(number);
	}

	int ans = numbers.size();
	cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		String t = scan.next();
		char[] cs = new char[s.length()];
		char[] ct = new char[t.length()];
		boolean[] count = new boolean[1001];
		int max = 0;
		
		for(int i=0;i<s.length();i++) {
			cs[i] = s.charAt(i);
		}
		
		for(int i=0;i<t.length();i++) {
			ct[i] = t.charAt(i);
		}
		
		for(int i=0;i<=s.length()-t.length();i++) {
			int n = 0;
			for(int j=0;j<t.length();j++) {
				if(cs[i+j] == ct[j]) {
					n++;
				}
			}
			max = Math.max(max, n);
			count[n] = true;
		}
		
		System.out.println(t.length()-max);

	}

}

Measured memory_bytes: 35692
#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
    string s;
    cin>>s;
    string t;
    cin>>t;
    vector<int> arr[26];
    for(int i = 0;i<s.length();i++){
        arr[s[i] - 'a'].push_back(i);
    }
    int dp[t.length()];
    bool possible = true;
    if(arr[t[0] - 'a'].size()){
        dp[0] = arr[t[0] - 'a'][0];
    }
    else{
        dp[0] = -1;
        possible = false;
    }
    long long totlen = dp[0] + 1;
    for(int i = 1;i<t.length() && possible;i++){
        int mini = dp[i-1];
        if(arr[t[i] - 'a'].size()){
            auto it = upper_bound(arr[t[i] - 'a'].begin(), arr[t[i] - 'a'].end(), mini);
            if(it!=arr[t[i] - 'a'].end()){
                dp[i] = *it;
                totlen+=dp[i] - dp[i-1];
            }
            else{
                dp[i] = arr[t[i] - 'a'][0];
                totlen+=(s.length() - dp[i-1]) + dp[i];
            }
        }
        else{
            possible = false;
        }
    }
    if(possible){
        cout<<totlen<<endl;
    }
    else{
        cout<<-1<<endl;
    }
}


Measured memory_bytes: 1468
using EducationalDPContest.Questions;
using EducationalDPContest.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace EducationalDPContest.Questions
{
    public class QuestionB : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var nk = inputStream.ReadIntArray();
            int n = nk[0];
            int k = nk[1];
            var h = inputStream.ReadIntArray();
            var dp = Enumerable.Repeat(int.MaxValue, n).ToArray();

            dp[0] = 0;

            for (int i = 1; i < n; i++)
            {
                for (int j = Math.Max(0, i - k); j < i; j++)
                {
                    dp[i] = Math.Min(dp[i], dp[j] + Math.Abs(h[i] - h[j]));
                }
            }

            yield return dp[n - 1];
        }
    }
}


namespace EducationalDPContest
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionB();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace EducationalDPContest.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace EducationalDPContest.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 21088
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
#define pi acos(-1)
const ll mod=1e9+9;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
const int N=100010;
ll n,c,ans;
struct node{ll x,v,s;}opt[N];
struct data{ll v;}as[N],iv[N];
int main()
{
	n=read();c=read();
	for(int i=1;i<=n;i++){
		opt[i].x=read();opt[i].v=read();
		//opt[i].x=i;opt[i].v=i;
		opt[i].s=opt[i].v+opt[i-1].s;
		as[i].v=as[i-1].v;
		if(opt[i].s-opt[i].x>as[i].v){
			as[i].v=opt[i].s-opt[i].x;
		}
	}
	for(int i=n;i>=1;i--){
		iv[i].v=iv[i+1].v;
		if(opt[n].s-opt[i-1].s-(c-opt[i].x)>iv[i].v){
			iv[i].v=opt[n].s-opt[i-1].s-(c-opt[i].x);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,opt[i].s-opt[i].x);
		ans=max(ans,opt[n].s-opt[i-1].s-(c-opt[i].x));
		ans=max(ans,opt[i].s-opt[i].x-opt[i].x+iv[i+1].v);
		ans=max(ans,opt[n].s-opt[i-1].s-(c-opt[i].x)-(c-opt[i].x)+as[i-1].v);
	}
	cout<<ans;
	return 0;
}

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

void f(int x, int &y, string &s, bool &a) {
  for (int i = y + 1; i < s.size(); i++) {
    char z;
    switch(x) {
      case 1:
        z = '1';
        break;
        case 2:
        z = '2';
        break;
        case 3:
        z = '3';
        break;
        case 4:
        z = '4';
        break;
        case 5:
        z = '5';
        break;
        case 6:
        z = '6';
        break;
        case 7:
        z = '7';
        break;
        case 8:
        z = '8';
        break;
        case 9:
        z = '9';
        break;
      default:
        z = '0';
        break;
    }
    if (s.at(i) == z) {
      y = i;
      a = true;
      break;
    }
  }
  return;
}

int main() {
	int n;
	string s;
  cin >> n >> s;
  int ans = 0;
  
  for (int i = 0; i < 10; i++) {
    int p = -1;
    bool a1 = false;
    f(i, p, s, a1);
    if (!a1) continue;
    for (int j = 0; j < 10; j++) {
      int q = p;
      bool a2 = false;
      f(j, q, s, a2);
      if (!a2) continue;
      for(int k = 0; k < 10; k++) {
        int r = q;
        bool a3 = false;
        f(k, r, s, a3);
        if (a3) {
          ans++;
        // cout << i << ":" << j << ":" << k << ":" << ans << endl;
        }
      }
    }
  }
  cout << ans << endl;

  /*
	string str = "000";
	str.at(0) = s.at(0);
	str.at(1) = s.at(1);
	str.at(2) = s.at(2);
	vector<string> vec = {str};
  for (int i = 0; i < n - 2; i++) {
		str.at(0) = s.at(i);
		for (int j = i + 1; j < n - 1; j++) {
			str.at(1) = s.at(j);
			for (int k = j + 1; k < n; k++) {
              str.at(2) = s.at(k);
              
				for (int l = 0; l < vec.size(); l++) {
					if (str == vec.at(l)) break;
                  else if (l == vec.size() - 1) vec.push_back(str);
                }
                
              }
		}
	}    

	cout << vec.size() << endl;
   for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
  }
*/
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if(a<b){
            if(b<=c){
                System.out.printf("%d %d %d\n",a,b,c);
            }else if(a>=c){
                System.out.printf("%d %d %d\n",c,a,b);
            }else if(a<c && c<b){
                System.out.printf("%d %d %d\n",a,c,b);
            }
        }else{
            if (a <=c) {
                System.out.printf("%d %d %d\n", b, a, c);
            } else if (b >=c) {
                System.out.printf("%d %d %d\n", c, b, a);
            }else if(b<c && c<a){
                System.out.printf("%d %d %d\n",b,c,a);
            }
        }
    }
}


Measured memory_bytes: 26364
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    string s;
    cin >> s;
    cout << s.substr(0, s.size()-8) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
using namespace std;
int main(){
	int n,k; ll ans=0;
	scanf("%d%d",&n,&k);
	if (k==0) ans=(ll)n*n;
	else{
		rep (b,k+1,n){
			//a%b>=k
			ans+=(ll)(b-k)*(n/b)+max(0,n%b-k+1);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(), x.end()
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const int MAX = 100005;

int main() {
    int n, c; cin >> n >> c;
    vvint d(c,vint(c));
    vvint x(3);
    rep(i,c)rep(j,c) cin >> d[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int a; cin >> a;
            x[(i+j)%3].push_back(a);
        }
    }
    // rep(j,3) {
    //     rep(i,c) cout << x[j][i] << " ";
    //     cout << endl;
    // }
    vvint y(3,vint(c));
    for (int color = 0; color < c; color++) {
        rep(i,3) {
            int sum = 0;
            rep(j,x[i].size()) {
                sum += d[x[i][j]-1][color];
            }
            y[i][color] = sum;
        }
    }
    // rep(j,3) {
    //     rep(i,c) cout << y[j][i] << " ";
    //     cout << endl;
    // }
    int ans = inf;
    rep(i,c) {
        rep(j,c) {
            if (i == j) continue;
            rep(k,c) {
                if (k == j || k == i) continue;
                ans = min(ans,y[0][i]+y[1][j]+y[2][k]);
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
    int n,k,h[100000];
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>h[i];
    sort(h,h+n);
    int ans=1000000000;
    for(int i=0;i<n-k+1;i++){
        int x=h[i];
        int y=h[i+k-1];
        if(y-x<ans)ans=y-x;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(){
	int i,n,a=0,h=0;
	int data[20];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&data[i]);
	}
	for(i=0;i<n;i++){
		if(h<=data[i]){
			a++;
			h=data[i];
		}
	}
	printf("%d",a);
	return 0;
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = 0
for i in range(n):
    for j in range(2):
        xi = min(a[i + j], b[i])
        a[i + j] -= xi
        b[i] -= xi
        x += xi
print(x)


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

#define ll long long
#define pb push_back
#define debug1(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x << "   " << #y << " = " << y << "\n";
#define _ ios_base::sync_with_stdio(0);cin.tie(NULL);

void solve() {
    int a;
    cin >> a;
    cout << (a + a*a + a*a*a) << '\n';
}

int main() {_
    int t = 1;
    //cin >> t;
    // Please remember to uncomment for taking test cases
    for(int i = 1; i<=t; i++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3640
S = input()
ALL, A, AB, ABC = 1, 0, 0, 0
mod = 10 ** 9 + 7

for s in S:
    if s == "A":
        A = (A + ALL) % mod

    if s == "B":
        AB = (AB + A) % mod

    if s == "C":
        ABC = (ABC + AB) % mod

    if s == "?":
        ABC = (ABC * 3 + AB) % mod
        AB = (AB * 3 + A) % mod
        A = (A * 3 + ALL) % mod
        ALL = (ALL * 3) % mod

print(ABC % mod)


Measured memory_bytes: 3188
import sys
sys.setrecursionlimit(100000)
INF = 1000000007
n,m= map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())

step = [0]*(n+10)
step[0] =1
step[1] =1
step[2] =2
for i in range(3,n+10):
    step[i] = step[i-1] + step[i-2]
if m != 0:
    l = [a[0]-1]
    for i in range(1,m):
        l.append(a[i]-a[i-1]-2)
    l.append(n-a[m-1]-1)

    ans = 1

    for i in range(m+1):
        if l[i] < 0:
            ans = 0
            break
        ans = ans*step[l[i]]
        if ans >= INF:
            ans = ans % INF
if m == 0:
    ans = step[n] % INF
print(ans)

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

int main() {
  set<int> S;

  S.insert(1);
  S.insert(3);
  S.insert(5);
  S.insert(7);
  S.insert(8);
  S.insert(10);
  S.insert(12);
  
  set<int> B;

  B.insert(4);
  B.insert(6);
  B.insert(9);
  B.insert(11);
  
    set<int> C;

  C.insert(2);
  
  int a, b ;
  cin >> a >> b ;
  
  cout << ( (S.count(a)&&S.count(b))||
           (B.count(a)&&B.count(b))||
           (C.count(a)&&C.count(b)) ?
           "Yes" : "No"
           )
    << endl;
}

Measured memory_bytes: 3608
H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]
mod = 10 ** 9 + 7

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[1][1] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if x == y == 1:
            continue
        else:
            if A[y-1][x-1] != '#' and (dp[y-1][x] > 0 or dp[y][x-1] > 0):
                dp[y][x] = dp[y-1][x] + dp[y][x-1]
print(dp[H][W] % mod)

Measured memory_bytes: 304912
using System;
using System.Collections.Generic;

namespace ITP1_4_D
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var input = Console.ReadLine();
            var values = input.Split(' ');
            List<int> num = new List<int>();
            long Sum = 0;
            for(int i=0; i<n; i++)
            {
                num.Add(int.Parse(values[i]));
                Sum += num[i];
            }
            num.Sort();
            Console.WriteLine("{0} {1} {2}", num[0], num[num.Count - 1], Sum);
        }
    }
}

Measured memory_bytes: 6692
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
 int x,y,tmp;

 while(1){
  cin >> x >> y;

  if(x == 0 && y == 0)break;

  if(x > y){
   tmp = x;
   x = y;
   y = tmp;
  }
  
  cout << x << " " << y << endl;
 }

 return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(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 ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

ll a[1000];
ll b[1000];
ll c[1000];

typedef tuple<int,int,int> P;

int main() {
  int X,Y,Z,K;
  while(input(X,Y,Z,K)) {
    inputs(a, X);
    inputs(b, Y);
    inputs(c, Z);
    sort(a, a+X);
    sort(b, b+Y);
    sort(c, c+Z);
    set<P> visited;
    priority_queue<pair<ll, P>> Q;
    auto p = P(X-1, Y-1, Z-1);
    visited.insert(p);
    Q.push(make_pair(a[X-1]+b[Y-1]+c[Z-1], p));
    REP(_, K) {
      auto q = Q.top(); Q.pop();
      ll score = q.first;
      output(score);
      auto p = q.second;
      REP(i,3) {
        int x = get<0>(p) - (i==0);
        int y = get<1>(p) - (i==1);
        int z = get<2>(p) - (i==2);
        if (x < 0 || y < 0 || z < 0) continue;
        P nxt(x,y,z);
        if (visited.count(nxt)) continue;
        visited.insert(nxt);
        Q.push(make_pair(a[x]+b[y]+c[z], nxt));
      }
    }
  }
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>

using namespace std;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, c;
	string str;
	cin >> n >> k >> c;
	cin >> str;
	vector<int> l, r;
	for (int i = 0; i < n; i++) {
		if (str[i] == 'x') continue;
		l.push_back(i + 1);
		if (l.size() == k) break;
		i += c;
	}
	for (int j = n - 1; j >= 0; j--) {
		if (str[j] == 'x') continue;
		r.push_back(j + 1);
		if (r.size() == k) break;
		j -= c;
	}
	sort(begin(r), end(r));
	vector<int> ans;
	for (int i = 0; i < k; i++) {
		if (l[i] == r[i]) {
			ans.push_back(l[i]);
		}
	}
	for (auto&& i : ans) {
		cout << i << "\n";
	}
}

Measured memory_bytes: 4236
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        bit = bit | (1 << (i - 1))
    S.append(bit)
P = list(map(int, input().split()))

ans = 0
for bit in range(1 << N):
    for i in range(M):
        p = S[i] & bit
        on = 0
        for j in range(N):
            if p & (1 << j):
                on += 1
        if (on % 2) != P[i]:
            break
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
    int n, x, y; cin >> n >> x >> y;

    // dist[i][j] = iからjへの最短距離
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

    // 頂点iから全頂点への最短距離を求める
    // N頂点に対しO(N)の幅優先探索を行うためO(N^2)
    for (int i = 0; i < n; ++i) {
        queue<int> que;
        que.push(i);
        dist[i][i] = 0;

        // 幅優先探索 O(N)
        while (!que.empty()) {
            int cur = que.front(); que.pop();

            vector<int> vs;
            vs.push_back(cur - 1);
            vs.push_back(cur + 1);
            if (cur == y - 1) vs.push_back(x - 1);
            if (cur == x - 1) vs.push_back(y - 1);

            for (auto v : vs) {
                if (v < 0 || n <= v) continue;
                if (dist[i][cur] + 1 < dist[i][v]) {
                    dist[i][v] = dist[i][cur] + 1;
                    que.push(v);
                }
            }
        }
    }

    // dist[k] = 最短距離がkな頂点の組み合わせの数
    vector<int> dists(n - 1, 0);

    // 「AからBへの最短距離」 から 「最短距離がKな頂点の組み合わせの数」 へ変換
    // nC2 = n * (n - 1) / 2 のループ O(N^2)
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ++dists[dist[i][j] - 1];
        }
    }

    for (auto ans : dists) {
        cout << ans << endl;
    }
}



Measured memory_bytes: 19040
#pragma comment(linker, "/STACK:500000000")
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <math.h>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <time.h>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const ll INF = static_cast<ll>(1e18);

int a[(int)1e5 + 9];
ll dp[(int)1e5 + 9][2];
ll sum[(int)1e5 + 9][2];

int main() {
	//freopen("in.txt", "rt", stdin);
	//freopen("out.txt", "wt", stdout);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	if (a[0] < 0) {
		dp[0][0] = 0;
		sum[0][0] = a[0];
		dp[0][1] = -a[0] + 1;
		sum[0][1] = 1;
	} else if(a[0] > 0) {
		dp[0][0] = a[0] + 1;
		sum[0][0] = -1;
		dp[0][1] = 0;
		sum[0][1] = a[0];
	} else {
		dp[0][0] = 1;
		sum[0][0] = -1;
		dp[0][1] = 1;
		sum[0][1] = 1;
	}
	for (int i = 1; i < n; ++i) {
		if (sum[i - 1][1] + a[i] < 0) {
			dp[i][0] = dp[i - 1][1];
			sum[i][0] = sum[i - 1][1] + a[i];
		} else if(sum[i - 1][1] + a[i] > 0) {
			dp[i][0] = dp[i - 1][1] + sum[i - 1][1] + a[i] + 1;
			sum[i][0] = -1;
		} else {
			dp[i][0] = dp[i - 1][1] + 1;
			sum[i][0] = -1;
		}

		if (sum[i - 1][0] + a[i] < 0) {
			dp[i][1] = dp[i - 1][0] - (sum[i - 1][0] + a[i]) + 1;
			sum[i][1] = 1;
		} else if(sum[i - 1][0] + a[i] > 0) {
			dp[i][1] = dp[i - 1][0];
			sum[i][1] = sum[i - 1][0] + a[i];
		} else {
			dp[i][1] = dp[i - 1][0] + 1;
			sum[i][1] = 1;
		}
	}
	printf("%lld\n", min(dp[n - 1][0], dp[n - 1][1]));
	return 0;
}

Measured memory_bytes: 3712
from itertools import combinations as comb

N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
dist = lambda a,b:((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5


def get_centers():
    ans = []
    for a, b, c in comb(l, 3):
        x1, y1 = a
        x2, y2 = b
        x3, y3 = c

        A = 2 * (x2-x1)
        B = 2 * (y2-y1)
        D = 2 * (x3-x2)
        E = 2 * (y3-y2)
        C = x1**2-x2**2+y1**2-y2**2
        F = x2**2-x3**2+y2**2-y3**2

        if B*D-A*E!=0:
            cy = (A*F-C*D)/(B*D-A*E)
            cx = -(F+E*cy)/D if D else -(C+B*cy)/A
            r = dist(a, (cx,cy))
            ans.append((cx, cy, r))

    for a, b in comb(l, 2):
        d = min(a,b)
        e = max(a,b)
        ans.append(((d[0]+e[0])/2, (d[1]+e[1])/2, dist(d,e)/2))

    return ans

if N==2:
    d = l[0]
    e = l[1]
    print(dist(d, e)/2)
else:
    ans = 10**12
    for xr, yr, r in get_centers():
        v = 0
        for x, y in l:
            v += dist((x,y),(xr,yr))<=r
        if v==N:
            ans = min(ans, r)
    print(ans)

Measured memory_bytes: 47216
#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>

using namespace std;

vector<string> V;

bool find(string s){
  for(int i = 0; i < V.size(); i++)
    if(V[i] == s) return true;

  return false;
}

int StoI(string s, int pos){

  string s1 = "", s2 = "";
  
  for(int i = 0; i < pos; i++)
    s1 += s[i];
  
  for(int i = pos; i < s.length(); i++)
    s2 += s[i];

  stringstream ss1(s1), ss2(s2);
  int n1,n2;
  ss1 >> n1;
  ss2 >> n2;
  return n1*n2;
}

string ItoS(int n){
  string out = "";
  if(n == 0) out = "0";

  while(n){
    out += n%10+'0';
    n /= 10;
  }
  reverse(out.begin(),out.end());
  return out;
}

string make(string n){
  int out = 0;

  for(int i = 1; i < n.length(); i++)
     out = max(out,StoI(n,i));

  return ItoS(out);
}

int solve(string n){
  
  int rev = 0;

  while(1){
    
    if(find(n)) return -1;
    else V.push_back(n);

    if(n.length() == 1) return rev;

    n = make(n);
    rev++;
  }
}

int main(){
  int n;
  cin >> n;
  while(n--){
    V.clear();
    string in;
    cin >> in;
    cout << solve(in) << endl;
  }
  return 0;
}

Measured memory_bytes: 1236
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		long arr[]=new long[n];
		HashMap<Long,Integer> h=new HashMap<>();
		for(int i=0;i<n;i++)
		{
			arr[i]=sc.nextLong();
			if(h.containsKey(arr[i]))
			{
				h.put(arr[i],h.get(arr[i])+1);
			}
			else
				h.put(arr[i],1);
			
		}
		long c=0;
		for(Map.Entry<Long, Integer> i:h.entrySet())
		{
			long k=i.getKey();
			long val=(long)i.getValue();
			if(k==1)
				c+=(Math.abs(k-val));
			else if(k==0)
				c+=val;
			else
			c+=(val%k);
		}
		
		System.out.println(c);
	}

}


Measured memory_bytes: 62768
'use strict';

function Main(input) {
    const tmp = input.split("\n")[0].split(" ");
    const a = tmp[0];
    const b = tmp[1];

    if (a == b) {
        console.log("H");
    } else {
        console.log("D");
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

using namespace std;

class node
{
public:
    int num;

public:
    int value = 0;

public:
    vector<int> to;
};

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

    int N;
    cin >> N;

    int Q;
    cin >> Q;

    vector<node> tree;

    for (int i = 0; i < N; i++)
    {
        node anode;
        anode.num = i;
        tree.push_back(anode);
    }

    int ai;
    int bi;

    vector<int> top;

    for (int i = 0; i < N - 1; i++)
    {
        cin >> ai;
        cin >> bi;
        ai--;
        bi--;
        tree[ai].to.push_back(bi);
    }

    int pi;
    int xi;

    vector<int> adds(N, 0);

    for (int i = 0; i < Q; i++)
    {
        cin >> pi;
        cin >> xi;
        pi--;

        adds[pi] += xi;
    }

    queue<node> que;

    que.push(tree[0]);

    while (true)
    {
        node front = que.front();

        tree[front.num].value += adds[front.num];

        if (front.to.size() > 0)
        {
            for (int j = 0; j < front.to.size(); j++)
            {
                que.push(tree[front.to[j]]);
                adds[front.to[j]] += tree[front.num].value;
            }
        }

        que.pop();

        if (que.empty())
        {
            break;
        }
    }

    for (int i = 0; i < N - 1; i++)
    {
        cout << tree[i].value << " ";
    }

    cout << tree[N - 1].value << endl;

    return 0;
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  string s; std::cin >> s;
  int n = s.size()-2;
  std::cout << s[0] << n << s.back() << "\n";
}


Measured memory_bytes: 256