akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if -1 in graph.distance_list():
    print("No")
else:
    print("Yes")
    print(*list(p+1 for p in graph.parent[1:]), sep="\n")


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

using namespace std;

typedef long long int li;
typedef vector<li> vi;
typedef pair<li,li> pi;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define f(i,l,r) for(li i=l;i<=r;++i)
#define fr(i,l,r) for(li i=l;i>=r;--i)
#define u_map unordered_map

li fastpow(li base,li exp,li M) 
{
    li res=1;
    while(exp>0) {
        if(exp&1)
            res=(res*base)%M;

        base=(base*base)%M;
        exp>>=1;
    }
    return res;
}
    
int main()
{    
    ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        li n;

        cin>>n;

        string s;

        cin>>s;

        li cnt=0;

        f(i,1,n-1)
        {
            if(s[i]!=s[i-1])
                cnt++;
        }

        cout<<cnt+1;

    return 0;
}

Measured memory_bytes: 512
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll mod =1e9+7;
const int N = 1e7+7;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)


int main()
{
    
    int a1,a2,a3,a4,a5;
    scf(a1),scf(a2),scf(a3),scf(a4),scf(a5);
    
    if(a1==0)
    prin(1);
    
    else if(a2==0)
    prin(2);
    
    else if(a3==0)
    prin(3);
    
    else if(a4==0)
    prin(4);
    
    else
    prin(5);
    
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++)
#define repr(i, n) for(int i = (n-1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define lint long long

int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x = x2 - x1; int y = y2 - y1;
    int x3 = x2 - y; int y3 = y2 + x;
    int x4 = x3 - x; int y4 = y3 - y;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;

using namespace std;

int main()
{
  int n;
  int a[200000];

  cin >> n;
  REP(i, n)
  {
    cin >> a[i];
  }

  int ans[200000] = {};
  int box = 0;

  for (int i = n - 1; i >= 0; i--)
  {
    int m = i + 1;
    int rep = 2;
    int sum = 0;
    while (rep * m <= n)
    {
      sum += ans[rep * m - 1];
      rep++;
    }

    if (sum % 2 == a[i])
    {
      ans[i] = 0;
    }
    else
    {
      ans[i] = 1;
      box++;
    }
  }

  cout << box << endl;

  REP(i, n)
  {
    if (ans[i] == 1)
    {
      cout << i + 1;
      if (i != n - 1)
      {
        cout << " ";
      }
    }
  }
  if (box != 0)
  {
    cout << endl;
  }
}


Measured memory_bytes: 2560
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    String[] s = in.readLine().split("");
    int x = 0;
    int max = 0;
    for(int i=0; i<n; i++) {
       if(s[i].charAt(0)=='I') {
        x++;
        max = Math.max(max,x);
      }
      if(s[i].charAt(0)=='D')
        x=x-1;
    }
    System.out.println(max);
  }
}

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

int main() {
  ll n, c;
  cin >> n >> c;
  vector<ll> x(n + 2), v(n + 2);
  for (int i = 0; i < n; i++) {
    cin >> x[i + 1] >> v[i + 1];
  }
  x[n + 1] = c;
  vector<ll> a(n + 2), b(n + 2);
  for (int i = 0; i < n; i++) {
    a[i + 1] = a[i] + v[i + 1] - (x[i + 1] - x[i]);
    b[n - i] = b[n - i + 1] + v[n - i] - (x[n - i + 1] - x[n - i]);
  }
  /*
  for (auto e : a) cerr << e << " ";
  cerr << endl;
  for (auto e : b) cerr << e << " ";
  cerr << endl;
  */
  for (int i = 0; i < n + 1; i++) {
    a[i + 1] = max(a[i], a[i + 1]);
    b[n - i] = max(b[n - i + 1], b[n - i]);
  }
  /*
  for (auto e : a) cerr << e << " ";
  cerr << endl;
  for (auto e : b) cerr << e << " ";
  cerr << endl;
  */
  ll m = max(a.back(), b.front());
  for (int i = 0; i < n + 1; i++) {
    m = max(m, a[i] + b[i + 1] - x[i]);
    m = max(m, b[n - i + 1] + a[n - i] - (c - x[n - i + 1]));
  }
  cout << m << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

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

	ll N, X, M; cin >> N >> X >> M;

	vector<bool> visited(M);

	vector<ll> A;
	A.push_back(X); visited[X] = true;
	ll x = X;
	while (1) {
		x = (x * x) % M;
		if (visited[x]) { break; }
		else { A.push_back(x); visited[x] = true; }
	}
	// x : ループの先頭
	// A : 先頭の部分 + ループ部分

	ll N1 = 0, N2 = 0;
	for (int i = 0; i < A.size(); i++) {
		if (A[i] == x) {
			N1 = i;
			N2 = A.size() - N1;
			break;
		}
	}

	ll sum = 0;
	for (int i = N1; i < A.size(); i++) { sum += A[i]; }

	if (N <= A.size()) {
		sum = 0;
		for (int i = 0; i < N; i++) {
			sum += A[i];
		}
		cout << sum << endl;
		return 0;
	}
	ll ans = 0;
	for (int i = 0; i < N1; i++) {
		ans += A[i];
	}
	N -= N1;
	ans += sum * (N / N2);
	N %= N2;
	for (int i = N1; i < N1 + N; i++) {
		ans += A[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3860
#include <stdio.h>

int main(int argc,char* argv[]){
  int i;
  double d;

  while(scanf("%lf",&d) != EOF){
    double sum = 0;
    sum += d;
    
    for(i = 2; i <= 10; i++){
      if(i % 2 == 0){
	d *= 2;
      }else{
	d /= 3;
      }

      sum += d;
    }

    printf("%lf\n",sum);
    
  }
  
  return 0;
  
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;
int main()
{
	int n,sum=1,a,b,c,i;
	scanf("%d %d",&a,&b);
	c=b-a; 
	for(i=2;i<c;i++)
	{
		sum+=i;
	}
	printf("%d\n",sum-a);
	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 repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define INF 1e9
#define all(v) v.begin(), v.end()
typedef long long ll;

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

  sort(all(a));
  rep(i, n) cout << get<2>(a[i]) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
 
int main(void){
      long n;
      cin >> n;
      vector<long> v(n);
      for(int i = 0;i < n;i++){
            cin >> v[i];
      }
      long ans = 0;
      for(int i = 0;i < n - 2;i++){
            for(int j = i + 1;j < n - 1;j++){
                  for(int k = j + 1;k < n;k++){
                        long a = v[i];
                        long b = v[j];
                        long c = v[k];
                        if(a == b || b == c || c == a)continue;
                        if(a + b > c &&  b + c > a && c + a > b)ans++;
                  }
            }
      }
      cout << ans << endl;
}

Measured memory_bytes: 3636
#include<bits/stdtr1c++.h>
#include<list>
#include<algorithm>
#include<cstdlib>
using namespace std;

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if ((abs(a-b)<=d && abs(b-c)<=d)||abs(a-c)<=d){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define PII pair<int,int>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

class Point
{
public:
	double x, y;
	Point(double X = 0, double Y = 0)
	{
		x = X;
		y = Y;
	}
	Point operator +(const Point &p)const { return Point(x + p.x, y + p.y); };
	Point operator -(const Point &p)const { return Point(x - p.x, y - p.y); };
	Point operator *(const double a)const { return Point(x*a, y*a); };
	Point operator /(const double a)const { return Point(x / a, y / a); };
	double norm()const { return x*x + y*y; };
	double length()const { return sqrt(norm()); };
	double dot(const Point &p)const { return x*p.x + y*p.y; };
	double cross(const Point &p)const { return x*p.y - y*p.x; };
	bool operator ==(const Point &p)const
	{
		return fabs(x - p.x)<EPS &&fabs(y - p.y)<EPS;
	}
	friend ostream& operator <<(ostream& os, const Point &p);
	int CCW(Point p1, Point p2)
	{
		Point p0(x, y);
		Point V1 = p1 - p0;
		Point V2 = p2 - p0;
		if (V1.cross(V2) > 0.0)return 1;
		else if (V1.cross(V2) < 0.0)return -1;
		else if (V1.dot(V2) < 0.0)return -2;
		else if (V1.norm() < V2.norm())return 2;
		return 0;
	}
};
typedef Point Vector;

ostream& operator <<(ostream& os, const Point &p)
{
	return os << "(" << p.x << "," << p.y << ")";
}

class Segment
{
public:
	Point p1, p2;
	Segment(double x1, double y1, double x2, double y2)
	{
		p1.x = x1;
		p1.y = y1;
		p2.x = x2;
		p2.y = y2;
	}
	double GetLength()
	{
		Point temp = p2 - p1;
		return temp.length();
	}
	double GetDistanceSeg(double X, double Y)
	{
		Point p(X, Y);
		Point a = p2 - p1;
		Point b = p - p1;
		Point c = p1 - p2;
		Point d = p - p2;
		if (a.dot(b) < 0.0)return b.length();
		if (c.dot(d) < 0.0)return d.length();
		return GetDistanceLine(X, Y);
	}

	double GetDistanceLine(double X, double Y)
	{
		Point t(X, Y);
		Point a = p2 - p1;
		Point b = t - p1;
		return abs(a.cross(b) / a.length());
	}
	bool IsIntersect(Segment &s)
	{
		int s1, s2;
		s1 = p1.CCW(p2, s.p1)*p1.CCW(p2, s.p2);
		s2 = s.p1.CCW(s.p2, p1)*s.p1.CCW(s.p2, p2);
		return s1 <= 0 && s2 <= 0;
	}
	bool IsOrthogonal(const Segment &s)
	{
		Vector t1 = p2 - p1;
		Vector t2 = s.p2 - s.p1;
		return equals(0.0, t1.dot(t2));
	}
	bool IsParallel(const Segment &s)
	{
		Vector t1 = p2 - p1;
		Vector t2 = s.p2 - s.p1;
		return equals(0.0, t1.cross(t2));
	}
	Point GetProjection(double X, double Y)const
	{
		Vector V = p2 - p1;
		Point P(X, Y);
		Point ret = V*(V.dot(P - p1) / V.norm());
		return ret + p1;
	}
	Point GetReflect(double X, double Y)
	{
		Point t(X, Y);
		Point Pro = GetProjection(X, Y);
		Vector dV = Pro - t;
		return t + dV*2.0;
	}
};
typedef Segment Line;

class Circle
{
public:
	Point c;
	double r;
	Circle(Point C = Point(), double R = 0)
	{
		c = C;
		r = R;
	}
};
int main()
{
	int q;
	cin >> q;
	REP(i, q)
	{
		int x0, y0, x1, y1, x2, y2, x3, y3;
		cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
		Segment s1(x0, y0, x1, y1), s2(x2, y2, x3, y3);
		cout << s1.IsIntersect(s2) << endl;
	}
	return 0;
}

Measured memory_bytes: 3096
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<set>

using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

int xs,ys,xg,yg;
int board[102][102];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

bool dfs(int x,int y,int c){
	if(board[y][x] != c) return false;
	if(x == xg && y == yg) return true;
	board[y][x] = 0;
	bool flag = false;
	for(int dir = 0;dir<4;dir++){
		if(dfs(x+dx[dir],y+dy[dir],c)){
			flag = true;
			break;
		}
	}
	return flag;
}

int main(){
	int w,h;
	int n,col;
	int c,d,x,y;
	int pos0_x[8] = {0,0,1,1,2,2,3,3};
	int pos0_y[8] = {0,1,0,1,0,1,0,1};
	int pos1_x[8] = {0,0,0,0,1,1,1,1};
	int pos1_y[8] = {0,1,2,3,0,1,2,3};

	while(true){
		cin>>w>>h;
		if(!w&&!h)break;
		cin>>xs>>ys>>xg>>yg>>n;
		for(y = 0;y<102;y++)
			for(x = 0;x<102;x++)
				board[y][x] = 0;
		for(int i = 0;i < n;i++){
			cin>>c>>d>>x>>y;
			if(d==0){
				for(int j = 0;j<8;j++)
					board[y+pos0_y[j]][x+pos0_x[j]] = c;
			}
			else{
				for(int j = 0;j<8;j++)
					board[y+pos1_y[j]][x+pos1_x[j]] = c;
			}
		}
		col = board[ys][xs];
		if(col==0)col=6;
		if(dfs(xs,ys,col))
			cout<<"OK"<<endl;
		else
			cout<<"NG"<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
using namespace std;

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

int main () {

    ll N,K;
    cin >> N >> K;

    if (K % 2 == 1) {
        ll t = N / K;
        cout << t * t * t << endl;
    } else {
        ll t1 = N / K;
        ll t2 = (N + K / 2) / K;
        cout << t1 * t1 * t1 + t2 * t2 * t2 << endl;
    }   

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s, t; cin >> s >> t;
	int n = s.length(), m = t.length();
	for (int i = n - m; i >= 0; i--){
		int flag = 1;
		for (int j = 0; j < m; j++){
			if (t[j] != s[i + j] && s[i + j] != '?'){
				flag = 0;
				break;
			}
		}
		if (!flag) continue;
		for (int j = 0; j < m; j++){
			s[i + j] = t[j];
		}
		for (int j = 0; j < n; j++){
			if (s[j] == '?') s[j] = 'a';
		}
		printf("%s\n", s.c_str());
		return 0;
	}
	printf("UNRESTORABLE\n");
	return 0;
}


Measured memory_bytes: 256
#include <string.h>
#include <stdio.h>
int main(void){
  double n=0;
  double m=0;
  double a[1000];
  int i;
  int t=0;
  double total=0;
  while(n<1 || n>100){scanf("%lf",&n);}
  while(m<1 || m>n){scanf("%lf",&m);}
  for(i=0;i<n;i++){
    while(a[i]<1 || a[i]>1000){scanf("%lf",&a[i]);}
    total=total+a[i];
  }
  for(i=0;i<n;i++){if(a[i]>=total/(4*m))t++;}
  if(t>=m)printf("Yes");
  else printf("No");
  return 0;
}


Measured memory_bytes: 1732
/*************************************************************************
> File Name: test.cpp
> Author: Akira 
> Mail: qaq.febr2.qaq@gmail.com 
************************************************************************/

#include<bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))
#define ALL(a) a.begin(), a.end()
#define mp make_pair
#define pb push_back
using namespace std;

#define MaxN 200005
#define MaxM MaxN*10
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
const int mod = 1E9+7;
const double eps = 1e-6;
#define bug cout<<88888888<<endl;
#define debug(x) cout << #x" = " << x << endl;
template<typename T> T abs(T val){return val>0?val:-val;}
inline int max2(int a, int b) {return ((a > b)? a : b);}
inline int min2(int a, int b) {return ((a < b)? a : b);}
inline int max3(int a, int b, int c) {return max2(a, max2(b, c));}
inline int min3(int a, int b, int c) {return min2(a, min2(b, c));}
template <class T> inline void read(T &ret) {char c; ret=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();}
template <class T> inline void out(T x) {if(x>9) out(x/10);putchar(x%10+'0');}

char str[MaxN];
int loc[MaxN][26], to[26], cost[MaxN];
void solve()
{
	int len = strlen(str);
	for(int i=0;i<26;i++) to[i] = len+1;
	for(int i=len;i>=0;i--)
	{
		memcpy(loc[i], to, sizeof(to));
		to[str[i-1]-'a'] = i;
	}
	for(int i=len;i>=0;i--)
	{
		cost[i] = len+5;
		for(int j=0;j<26;j++)
		{
			cost[i] = min(cost[i], cost[loc[i][j]]+1);
		}
	}
	int u = 0,v;
	while(u!=len+1)
	{
		for(v=0;v<26;v++)
		{
			if(cost[u]==cost[loc[u][v]]+1) break;
		}
		printf("%c", v+'a');
		u = loc[u][v];
	}
	puts("");
}
int main()
{
    //std::ios::sync_with_stdio(false);
	while(~scanf("%s", &str))
	{
		solve();
	}
    //system("pause");
    //printf("%lld\n", ((x)%mod+mod)%mod );
    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
}


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

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -float("inf")
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

n = int(input())
P = list(map(int, input().split()))
seg = RmaxQ(P)

def bs(i, p, right):
  if right:
    ok = i
    ng = n
    while ng - ok > 1:
      mid = (ok + ng) // 2
      if seg.query(i+1, mid+1) > p:
        ng = mid
      else:
        ok = mid
  else:
    ok = i
    ng = -1
    while ok - ng > 1:
      mid = (ok + ng) // 2
      if seg.query(mid, i) > p:
        ng = mid
      else:
        ok = mid
  return ng

ans = 0
for i, p in enumerate(P):
  r1 = bs(i, p, True)
  r2 = bs(r1, p, True)
  l1 = bs(i, p, False)
  l2 = bs(l1, p, False)
  ans += p * ((l1-l2)*(r1-i) + (i-l1)*(r2-r1))
print(ans)

Measured memory_bytes: 101636
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

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

struct edge{int to,cost;};

char a[8][8];
int h,w;

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

	cin >> h >> w;

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> a[i][j];
		}
	}
	int i=0,j=0;
	a[0][0]='.';
	while(true){
		if(i==h-1 && j==w-1)  break;
		if(j<w-1 && a[i][j+1]=='#'){
			j++;
			a[i][j]='.';
		}else if(i<h-1 && a[i+1][j]=='#'){
			i++;
			a[i][j]='.';
		}else{
			cout << "Impossible\n";
			return 0;
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(a[i][j]=='#'){
				cout << "Impossible\n";
				return 0;
			}
		}
	}
	cout << "Possible\n";
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
typedef long long LL;
#define int LL
int readint(){
	int x=0,f=1;char s=getchar();
	#define sc (s=getchar())
	while(s<'0'||s>'9'){
		if(s=='-')
			f=-1;
		sc;
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);
		sc;
	}
	#undef sc
	return x*f;
}
signed main(){
	int x=readint();
	double be=100,nian=0;
	while(be<x){
		nian++,be=floor(1.0*be*1.01);
	}
	cout<<nian;
	return 0;
}

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

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int k;
  cin >> k;
  vector<ll> q;
  ll x;
  for (int i = 1; i <= 9; ++i) q.push_back(i);
  for (int i = 0; i < k; ++i) {
    x = q[i];
    for (int j = -1; j <= 1; ++j) {
      if (x%10 + j < 0 || x%10 + j > 9) continue;
      q.push_back(x*10+(x%10+j));
    }
  }
  cout << x << endl;
}

Measured memory_bytes: 6384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod=1000000007;
const double PI = 3.14159265359;
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define INF 1000000000000
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define FOR(i,n) for(int i=0;i<(n);i++)
#define FORA(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define count_1(n)  __builtin_popcountll(n)
#define parity(n)   __builtin_parityll(n)   //Even parity 0 as output
void show    (int a[], int arraysize) { for (int i = 0; i < arraysize; ++i)  {cout << a[i] << " ";}	cout<<endl;}
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
void sieve(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}
int main()
{FAST
int c=0;
string s,t;
cin>>s>>t;
FOR(i,s.size())
{
	if(s[i]!=t[i])
	{
		c++;
	}
}
cout<<c<<endl;
return  0;
}






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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int64_t x; cin>>x;
	int64_t ans=x/11*2;
	if(int y=x%11){
		if(y>6)++ans;
		++ans;
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int main()
{
    int a;
    cin>>a;
    long long int sum=0;
    for(int i=1;i<=a;i++)
    {
        if(i%5!=0&&i%3!=0)
        {
            sum+=(long long int)i;
        }
    }
    cout<<sum;
    return 0;
}




Measured memory_bytes: 3192
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

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

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

void fast_input() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

pair<char, int> solve(int N) {
    vector<int> cans(30);
    vector<int> C(N);
    pair<char, int> ret = {'A', -1};
    for (int i = 0; i < N; i++) {
        int flag = 0;
        string s; cin >> s;
        char c = s[0];
        if (flag) continue;
        C[i] = (int)(c - 'A');
        cans[C[i]]++;
        int ma = -1;
        int top = -1;
        int second_top = -1;
        int second_ma = -1;
        for (int j = 0; j < 30; j++) {
            if (ma < cans[j]) {
                ma = cans[j];
                top = j;
            }
        }
        for (int j = 0; j < 30; j++) {
            if (top == j) continue;
            if (second_ma < cans[j]) {
                second_ma = cans[j];
                second_top = j;
            }
        }
        if (ma > second_ma + (N - i - 1)) {
            ret = {'A' + top, i+1};
            for (int j = i + 1; j < N; j++) {
                cin >> c;
            }
            break;
            flag = 1;
        }
    }
    return ret;
}

int main(void) {
    int N;
    vector<pair<char, int>> ans;
    while (1) {
        cin >> N;
        if (N == 0) break;
        ans.push_back(solve(N));
    }
    for (auto &p : ans) {
        if (p.second != -1) {
            cout << p.first << " " << p.second << endl;
        } else {
            cout << "TIE" << endl;
        }
    }    
}   



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

const int MAX = (int)2e5 + 7;
int monsters[MAX];
int main() {
	int n, k;
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
		cin >> monsters[i];
	
	sort(monsters, monsters + n);
	
	int attacksNo = n - k;
	long long ans = 0;
	for(int i = 0; i < attacksNo; i++)
		ans += (long long)monsters[i];
		
	cout << ans;
	return 0;
}

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

using namespace std;

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

const int N = 1000005;
ll dpD[N], dpM[N], dpC[N], dpDM[N];

inline ll calc(int i, int j) {
	ll ans = dpDM[j + 1] - dpDM[i];
	ans -= dpD[i] * (dpM[j + 1] - dpM[i]);
	return ans;
}

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n, q;
	string s;

	cin >> n >> s >> q;

	dpD[0] = dpM[0] = dpC[0] = dpDM[0] = 1;
	REPU(i, 0, n) {
		dpD[i + 1] = dpD[i] + (s[i] == 'D' ? 1 : 0);
		dpM[i + 1] = dpM[i] + (s[i] == 'M' ? 1 : 0);
		dpC[i + 1] = dpC[i] + (s[i] == 'C' ? 1 : 0);
		dpDM[i + 1] = dpDM[i];

		if (s[i] == 'M') {
			dpDM[i + 1] += dpD[i];
		}
	}

	REPU(_, 0, q) {
		int k; cin >> k;
		ll ans = 0;
		REPU(i, 2, n) if (s[i] == 'C') {
			int from = max(0, i - k + 1);
			int to = i - 1;

			ans += calc(from, to);
		}
		printf("%lld\n", ans);
	}

	return 0;
}


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

int main() {
    long long a, b;
    cin >> a >> b;
    if ((b-a)%2==0) {
        cout << abs(b-a)/2 + min(a, b) << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        string[] R = Console.ReadLine().Split(" ");

        int N = int.Parse(R[0]);
        int M = int.Parse(R[1]);


        string[] R_ = Console.ReadLine().Split(" ");

        int[] x = new int[R_.Length];

        for (int i = 0; i < R_.Length; i++)
        {
            x[i] = int.Parse(R_[i]);
        }

        int M_sum =x.Sum();

        int result = N - M_sum;

        if (result >= 0)
        {
            System.Console.WriteLine(result);
        }
        else 
        {
            System.Console.WriteLine(-1);
        }
    }
}


Measured memory_bytes: 29016
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main(){
    string str;
    cin>>str;
    ll res = 0, i=0;
    ll x = str.length(); 
    while(i<x){
        res+=str[i]-'0';
        i++;
    }
    if(res%9 == 0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3664
/* _________________________________________________________________________________________________
  |                                                                                                 |
  |                             Author      : Aditya Ahuja                                          |
  |                             Date        : Mon,  3rd June 2019                                   |
  |_________________________________________________________________________________________________|
*/
 
#include<bits/stdc++.h>
using namespace std;

#define pb          push_back
#define F           first
#define S           second
#define rep(i,a,b)  for(int i=a; i<b; i++)
#define all(a)      (a).begin(),(a).end()
#define wa(x)       cout << (#x) << " -------- " << (x) << endl
#define line1	    printf("---------------------------\n")

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

void pvi(auto v){
	for(auto it:v) cout << it << " ";
	cout << endl;
}

void solve();
signed main() {
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	////cout << fixed << setprecision(10);

	int t=1; 
	//cin>>t;
	while(t--) solve();
	return 0;
}

//___________________________________________________________________________________________________

void solve() {

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

	vi a(n,0);
	rep(i,0,n) cin>>a[i];

	vi b(n,0);
	b[0] = 0;

	rep(i,1,n){

		int mn = 1e9;

		rep(j,1,k+1){
			if(i-j < 0) continue;
			mn = min(mn, b[i-j] + abs(a[i]-a[i-j]));
		}
		b[i] = mn;
	}

	cout << b[n-1] << endl;
}


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

int main(){
  int n; cin>>n;
  int num[n+1];
  for(int i=0;i<n+1;i++){
    if(i==0) num[i]=0;
    else{
      cin>>num[i];
    }
  }int ans[n+1];
  for(int i=n;i>1;i--){
    if(n/i<2) ans[i]=num[i];
    else{
      int c=0;
      for(int j=2;j*i<=n;j++){
        c+=ans[j*i];
      }if(c%2==num[i]) ans[i]=0;
      else ans[i]++;
    }
  }vector<int> report;
  int sum=0;
  for(int i=2;i<=n;i++){
    if(ans[i]>0){
      sum++;
      report.push_back(i);
    }
  }if(sum%2!=num[1]) report.push_back(1);
  if(report.empty()){
    cout<<0<<endl;
  }else{
    cout<<report.size()<<endl;
    sort(report.begin(),report.end());
    for(int i=0;i<report.size()-1;i++){
      cout<<report[i]<<' ';
    }cout<<report[report.size()-1]<<endl;
  }
}

Measured memory_bytes: 3064
#include "iostream"

using namespace std;

int main() {
  /* code */
  int n, s1 = 0, s2 = 0, s3, ans;
  int w1[100], w2[100];
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> w1[i];
    s1 += w1[i];
  }
  s3 = s1 - w1[0];
  if (w1[0] - s3 > 0) {
    w2[1] = w1[0] - s3;
    ans = w1[0] - s3;
  } else {
    w2[1] = s3 - w1[0];
    ans = s3 - w1[0];
  }
  for (int i = 2; i < n; i++) {
    for (int j = 0; j < i; j++) {
      s2 += w1[j];
    }
    s3 = s1 - s2;
    if (s2 - s3 > 0) {
      w2[i] = s2 - s3;
    } else {
      w2[i] = s3 - s2;
    }
    if (w2[i] < ans) {
      ans = w2[i];
    }
    s2 = 0;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  if (b - a < 2 * k) {
    for (int i = a; i < b + 1; i++) {
      cout << i << endl;
    }
  }
  else {
    for (int i = a; i < a + k; i++) {
      cout << i << endl;
    }
    for (int j = b - k + 1; j < b + 1; j++) {
      cout << j << endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void)
{
    char str[21];
    int i=0;
    while(cin>>str[i])
    {
        i++;
    }
    for(int j=i-1;j>=0;j--)
    {
        cout<<str[j];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3080
#include <iostream>
#include <cmath>
#include <utility>

using namespace std;

int gcd(int a, int b){
    if(a<b) swap(a,b);
    int c = a%b;
    if(c==0) return b;
    else return gcd(b,c);
}
int main(){
    int N,X;
    cin >> N >> X;
    int x[N];
    int d[N];
    for(int i=0; i<N; i++){
        cin >> x[i];
        d[i] = abs(X-x[i]);
    }
    int ans = d[0];
    for(int i=1; i<N; i++){
        if(ans == 0) ans = d[i];
        else if(d[i] != 0) ans = gcd(ans,d[i]);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 1024
#include <iostream>
using namespace std;
 
int main() {
  int a,b,c,d,e,g,v,ans,i,j;
  char ci[4],x,z='0';
  while (true) {
	 cin >> ci;
	 if (ci[0]==z && ci[1]==z && ci[2]==z && ci[3]==z) break;
	 ans=0; g=0;
	 if (ci[0]==ci[1] && ci[1]==ci[2] && ci[2]==ci[3]) { cout << "NA" << endl; continue;}
	 if (ci[0]=='6' && ci[1]=='1' && ci[2]=='7' && ci[3]=='4') g=6174;
	 while(g!=6174) {
	 ans++;
	 for (i=2;i>=0;i--) for (j=0;j<=i;j++) if (ci[j]<ci[j+1]) { x=ci[j+1]; ci[j+1]=ci[j]; ci[j]=x;}
	 a=ci[0]-z; b=ci[1]-z; c=ci[2]-z; d=ci[3]-z;
	 e=1000*(a-d)+100*(b-c)+10*(c-b)+d-a; g=e;
	 for (i=0,v=1000;i<4;i++,v/=10) { ci[i]='0'+e/v; e-=(e/v)*v;} 
	 }
     cout << ans << endl;
  }	 
  return 0;
} 

Measured memory_bytes: 1140
#include <iostream>
#include <queue>
#include <string>
#define rep(i,a) for(i = 0; i < a; i++)
using namespace std;

struct Process {
  string name;
  int time_i;
};

int main(void) {

  int i,n,q,TotalTime = 0;
  queue<Process> qu;
  Process tmp;

  cin >> n >> q;
  rep(i,n) {
    cin >> tmp.name >> tmp.time_i;
    qu.push(tmp);
  }

  while(!qu.empty()) {
    tmp = qu.front();
    qu.pop();
    if(tmp.time_i - q > 0) {
      tmp.time_i =tmp.time_i - q;
      TotalTime += q;
      qu.push(tmp);
    } else {
      TotalTime += tmp.time_i;
      cout << tmp.name << " " << TotalTime << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 4404
N = int(input())
A = list(map(int, input().split()))

A.sort()
D = [1]
t = A[0]
for i in range(1, N):
  if A[i] == t:
    D[-1] += 1
  else:
    D.append(1)
    t = A[i]

D.sort()
L = len(D)
S = [0] * L
S[0] = D[0]
for i in range(1, L):
  S[i] = S[i - 1] + D[i]

def hersCode(n):
  ok = 0
  ng = N + 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid, n):
      ok = mid
    else:
      ng = mid
  return ok

def honya(n):
  ok = -1
  ng = L
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok + 1

def nasu(x, n):
  a = honya(x)
  ans = a * x + S[L - a - 1]
  if ans >= n * x:
    return True
  else:
    return False

D.sort(reverse = True)
for i in range(1, N + 1):
  if L < i:
    print(0)
    continue
  print(hersCode(i))

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[200002];

int main() {
	cin >> n;
	a[0] = -1;
	inc1(i, n) { cin >> a[i]; }
	a[n + 1] = 0;
	
	LL ans = 0;
	bool f = true;
	decII(i, 0, n) {
		if(a[i] + 1 < a[i + 1]) { f = false; }
		if(a[i] + 1 > a[i + 1]) { ans += a[i]; }
	}
	if(! f) { ans = -1; }
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n, w;
        cin >> n >> w;
        if(n == 0)
            return 0;

        map<int, int> h;
        int maxH = 0;
        int right = 0;
        for(int i=0; i<n; ++i){
            int v;
            cin >> v;
            maxH = max(maxH, ++ h[v/w]);
            right = max(right, v/w);
        }

        map<int, int>::iterator it;
        double ret = 0.01;
        for(it=h.begin(); it!=h.end(); ++it)
            ret += (double)(right - it->first) / right / maxH * it->second;

        printf("%.10f\n", ret);
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>

using namespace std;

int main(){
  long long x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vector <long long> crv(a);
  for (long long i = 0; i < a; i++)
   cin >> crv[i];
  vector <long long> zel(b);
  for (long long i = 0; i < b; i++)
   cin >> zel[i];
  vector <long long> bb(c);
  for (long long i = 0; i < c; i++)
   cin >> bb[i];
  sort(crv.begin(),crv.end());
  sort(zel.begin(),zel.end());
  sort(bb.begin(),bb.end());
  vector <long long> nn;
  for (long long i = 0; i < x; i++)
   nn.push_back(crv[a-1-i]);
  for (long long i = 0; i < y; i++)
   nn.push_back(zel[b-1-i]);
  for (long long i = 0; i < min(c,x+y); i++)
   nn.push_back(bb[c-1-i]);
  sort(nn.begin(),nn.end());
  long long suma = 0;
  for (long long i = 0; i < x + y; i++)
   suma += nn[x+y+min(c,x+y)-1-i];
  cout << suma;
}

Measured memory_bytes: 8304
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:1024000000")
#pragma warning( disable : 6031)
#pragma warning( disable : 4244)
#pragma warning( disable : 26451)
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-15)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef vector<ll> vl;
typedef vector<vector<long long>> vvl;
typedef tuple<int, int, int> tiii;
const long long mod = int(1e9) + 7;
const int INF = 1e9;


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif

	string as = "", bs = "";
	int a, b;
	cin >> a >> b;
	for (int i = 0; i < a; i++)
		as += (b + '0');
	for (int i = 0; i < b; i++)
		bs += (a + '0');
	if (as < bs)
		cout << as;
	else
		cout << bs;

	return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    S = [0] * (N+1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    ans = 10**19
    for i in range(1, N):
        a = S[i] - S[0]
        b = S[N] - S[i]
        ans = min(ans, abs(a-b))
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> s(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> s[i][j];
        }
    }

    long long ans = 0;
    vector<int> di = {-1, 0, 1, 0}, dj = {0, -1, 0, 1};
    vector<vector<bool>> done(h, vector<bool>(w, false));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (done[i][j] == false) {
                long long white = 0, black = 0;
                if (s[i][j] == '.') {
                    white++;
                } else {
                    black++;
                }
                queue<pair<int, int>> que;
                done[i][j] = true;
                que.push({i, j});
                while (que.size() > 0) {
                    auto pos = que.front();
                    que.pop();
                    int pi = pos.first, pj = pos.second;
                    for (int k = 0; k < 4; k++) {
                        int ni = pi + di[k], nj = pj + dj[k];
                        if (0 <= ni and ni < h and 0 <= nj and nj < w) {
                            if (done[ni][nj] == false and s[pi][pj] != s[ni][nj]) {
                                if (s[ni][nj] == '.') {
                                    white++;
                                } else {
                                    black++;
                                }
                                done[ni][nj] = true;
                                que.push({ni, nj});
                            }
                        }
                    }
                }
                ans += white * black;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var str=(input.trim()).replace(/egg/g,"E").replace(/chicken/g,"C");
while(/EE/.test(str))str=str.replace(/EE/g,"EAE");
while(/CC/.test(str))str=str.replace(/CC/g,"CAC");
var ary=str.split("A");
var ans="";
ary.forEach(function(v){
   if(ans.length<v.length)ans=v;
});
console.log((ans.slice(-1)=="E")?"egg":"chicken");

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

int main(void)
{
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    int train_min , bus_min;
    if(A >= B)
        train_min = B;
    else 
        train_min = A;

    if(C >= D)
        bus_min = D;
    else
        bus_min = C;
    
    cout << bus_min + train_min << endl;

}


Measured memory_bytes: 256
from math import sqrt
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        Y = X[i]
        Z = X[j]
        d = sqrt(sum([(y - z) ** 2 for y, z in zip(Y, Z)]))
        if float(int(d)) == d:
            ans += 1
print(ans)

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



int main(){
  int a, b, n; cin >> a >> b >> n; int c[a], d[b];
  int minc=inf, mind=inf, ans=inf;
  rep(i, a){
    cin >> c[i]; minc = min(minc, c[i]);
  }
  rep(j, b){
    cin >> d[j]; mind = min(mind, d[j]);
  }
  ans = minc+mind;
  rep(i, n){
    int x, y, z; cin >> x >> y >> z; x--; y--;
    ans = min(ans, c[x]+d[y]-z);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
INF = float("inf")
n = int(input())
z = []
m = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    a, b = map(int, input().split())
    z.append(a)
z.append(b)
for l in range(1, n):
    for i in range(1, n - l + 1):
        j = i + l
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + z[i - 1] * z[k] * z[j])
print(m[1][n])



Measured memory_bytes: 5672