akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;

int main() {
  ll V, E, r;  cin >> V >> E >> r;
  vector<vector<pair<ll, ll>>> map(V);
  rep(i, E) {
    ll s, t, d; cin >> s >> t >> d;
    map[s].push_back(make_pair(t, d));
//    map[t].push_back(make_pair(s, d));
  }
  
  ll dis[V]; memset(dis, -1, sizeof(dis));
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
  pq.push(make_pair(0, r));
  dis[r] = 0;
  vector<bool> checked(V, false);
  while(!pq.empty()) {
    auto p = pq.top(); pq.pop();
    ll a = p.second, b = p.first;
    if (checked[a] == true) continue;
    checked[a] = true;
    dis[a] = b;
    
    for (auto v : map[a]) {
      pq.push(make_pair((b + v.second), v.first));
//      dis[v.first] = b + v.second;
    }
  }
  
  rep(i, V) {
    if (dis[i] == -1)  cout << "INF" << endl;
    else  cout << dis[i] << endl;
  }
}


Measured memory_bytes: 21456
#!/Users/takahiro.kida/git/atcorder/venv/bin/python

import numpy
import scipy

from collections import defaultdict
from pprint import pprint

N = int(input())
h = [int(x) for x in input().split(" ")]

f = [0 for i in range(N)]

def update_f():
    start = False
    for i in range(N):
        if start and f[i] < h[i]:
            f[i] = f[i] + 1
            continue
        if start and f[i] >= h[i]:
            break
        if f[i] < h[i]:
            start = True
            f[i] = f[i] + 1
    if start:
        return False
    else:
        return True

cnt = 0
while True:
    if update_f():
        break
    else:
        cnt += 1

print(cnt)


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

using namespace std;

#define sqr(x) ((x) * (x))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef vector<int> vi;
typedef map<int, int> mi;
typedef pair<int, int> pi;
typedef long long ll;

void solve() {
  string S;
  cin >> S;
  int hi = atoi(S.substr(0, 2).c_str());
  int lo = atoi(S.substr(2, 2).c_str());
  if ((hi == 0 || hi > 12) && (lo == 0 || lo > 12)) {
    cout << "NA" << endl;
  } else if (hi >= 1 && hi <= 12) {
    if (lo == 0 || lo > 12) {
      cout << "MMYY" << endl;
    } else {
      cout << "AMBIGUOUS" << endl;
    }
  } else {
    if (lo >= 1 && lo <= 12) {
      cout << "YYMM" << endl;
    } else {
      cout << "AMBIGUOUS" << endl;
    }
  }
}

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

  solve();

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const bool debug = false;
int main(){
    string s,t;
    cin >> s >> t;
    vector<int> dp(t.size()), p(t.size());
    vector<vector<int>> lst(s.size());
    rep(i,s.size()){
        swap(dp,p);
        rep(j,t.size()){
            if(s.at(i) == t.at(j)){
                if(j == 0) p[j]  = 1;
                else p[j] = dp[j-1] + 1;
            }
            else {
                if(j==0) p[j] = dp[j];
                else p[j] = max(p[j-1],dp[j]);
            }
        }
        lst.at(i) = p;    
    }

    if(debug){
        rep(i,s.size()){
            rep(j,t.size()){
                cout << lst[i][j] << " ";
            }
            cout << endl;
        }
    }

    stack<char> stk;
    int i=s.size()-1;
    int j=t.size()-1;
    while(i>0 || j>0){
        if(debug) cout << "i,j = " << i << " " << j << endl;
        if(i > 0 && j > 0){
            if(s.at(i) == t.at(j)){
                stk.push(s.at(i));
                i--;
                j--;
            }
            else{
                if(lst.at(i).at(j-1) < lst.at(i-1).at(j)) i--;
                else j--;
            }
        }
        else if(i > 0){
            if(lst.at(i).at(j) != lst.at(i-1).at(j)){
                stk.push(s.at(i));
            }
            i--;
        }
        else {
            if(lst.at(i).at(j) != lst.at(i).at(j-1)){
                stk.push(s.at(i));
            }
            j--;
        }
    }
    if(lst[0][0] == 1) stk.push(s.at(0));

    while(!stk.empty()){
        cout << stk.top();
        stk.pop();
    }
    cout << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
#define tr(container, it) \
        for (auto it = container.begin(); it != container.end(); it++)
#define scontains(c, x) ((c).find(x) != (c).end())   //O(log n)
#define contains(c, x) (find((c).begin(),(c).end(),x) != (c).end()) //O(n)
#define ill(_x)  ll _x;scanf("%lld",&_x);
#define idb(_x)  double _x;scanf("%lf",&_x);
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vs vector<string>
#define in0(x, a, b)((x)>=a && (x)<=b    )
#define in1(x, a, b)((x)>a && (x)<b)
#define  rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const double pi = 3.14159265358979323846;
const int INF = 0x3f3f3f3f;
const int X10 = 1024, X11 = 2048, X12 = 4096, X13 = 8196, X14 = 16392, X15 = 32786, X16 = 65536, X17 = 131072, X18 = 262144, X19 = 524288, X20 = 1048576;

class UnionFind {
private:
    vector<int> p, rank;
    int N;
    int findSet2(int i, bool* A){A[i] = 1;return (p[i] == i) ? i : (p[i] = findSet2(p[i], A));}
public:
    UnionFind(int N) {
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++) p[i] = i;
        this->N = N;
    }

    int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }

    bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }

    void unionSet(int i, int j) {
        if (!isSameSet(i, j)) {
// if from different set
            int x = findSet(i), y = findSet(j);
            if (rank[x] > rank[y]) p[y] = x;
// rank keeps the tree short
            else {
                p[x] = y;
                if (rank[x] == rank[y]) rank[y]++;
            }
        }
    }


    int numDisjointSets(){
        set<int> s;
        bool* visited = new bool[this->N];
        memset(visited, 0, sizeof(bool)*this->N);
        for (int i = 0; i < N; ++i) {
            if(!visited[i])s.insert(findSet2(i, visited));
        }
        return s.size();
    }

    int maxElements(){
        int mx = 0;
        map<int, int> m;
        for (int i = 0; i < N; ++i) {
            m[findSet(i)] ++;
        }
        set<pair<int, int>> s;
        for(auto p : m){
            s.insert({p.second, p.first});
        }
        return s.rbegin()->first ;
    }


};

ll A[100000];
void _() {
    int n;
    cin >> n;
    int t = 2;
    for (int i = 0; i < 17; ++i) {
        n += t;
        t *=4;
    }
    bitset<32> s(n);
    bool ok = 0;
    for (int i = 31; i > -1; --i) {
        if(i % 2 ){
            if(!s[i])ok=1;
            if(ok)cout << !s[i];
        }
        else {
            if(s[i])ok=1;
            if(ok)cout << s[i];
        }
    }
    if(!ok)cout << 0;
//    cout << s.to_string();

}


int main() {
#ifdef Debug
    freopen("/home/joduskame/Desktop/cpp/IO/Input.txt", "r", stdin);
    freopen("/home/joduskame/Desktop/cpp/IO/Output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    _();
    return 0;

}








Measured memory_bytes: 256
"""import sys
input = sys.stdin.readline().strip"""
h,w=map(int,input().split())
#print(h,w)
s=[input() for _ in range(h)]
#print(s)
ans=[["#"]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        cnt=0
        for k in [-1,0,1]:
            for l in [-1,0,1]:
                if k==0 and l==0:
                    continue
                if 0<=i+k<h and 0<=j+l<w:
                    if s[i+k][j+l]=="#":
                        cnt+=1
        ans[i][j]=cnt
#print(ans)
for a in ans:
    #print(a)
    print("".join(map(str,a)))


Measured memory_bytes: 41328
#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a, _b = b; i <= _b; ++i)
#define Ford(i, a, b) for(int i = a, _b = b; i >= _b; --i)
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long long
#define Print(x)      cerr << #x << "is " << x << '\n';
#define pb            push_back
#define X             first
#define Y             second
//#define Karma

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 2e5 + 7;

ll f[N], g[N];
int n, u, v, mod;
vector<int> a[N];

void DFS(int u, int par)
{
    int pos = -1, sz = a[u].size();
    for(int i = 0; i < sz; ++i)
    {
        int v = a[u][i];
        if(v == par) {pos = i; continue;}
        DFS(v, u);
    }
    if(pos != -1) a[u][pos] = a[u].back(), a[u].pop_back(), --sz;
    f[u] = 1;
    for(int v: a[u]) f[u] = (f[u] * (f[v] + 1)) % mod;
}

void DFS2(int u)
{
     if(a[u].empty()) return;
     int sz = a[u].size();
     vector<ll> pre(sz), suf(sz);
     for(int i = 0; i < sz; ++i)
     {
         int v = a[u][i];
         if(i) pre[i] = pre[i - 1] * (f[v] + 1) % mod;
         else pre[i] = (f[v] + 1) % mod;
     }
     for(int i = sz - 1; i > 0; --i)
     {
         int v = a[u][i];
         if(i < sz - 1) suf[i] = suf[i + 1] * (f[v] + 1) % mod;
         else suf[i] = (f[v] + 1) % mod;
     }
     ll Pre, Suf;
     for(int i = 0; i < sz; ++i)
     {
         int v = a[u][i];
         Pre = 1, Suf = 1;
         if(i) Pre = pre[i - 1];
         if(i < sz - 1) Suf = suf[i + 1];
         g[v] = ((Pre * Suf % mod) * g[u] + 1ll) % mod;
         DFS2(v);
     }
}

void Enter()
{
     Cin(n, mod);
     For(i, 2, n) Cin(u, v), a[u].pb(v), a[v].pb(u);
     DFS(1, 0);
     g[1] = 1;
     DFS2(1);
     For(i, 1, n) Cout(g[i] * f[i] % mod, '\n');
}

void Solve()
{

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(FileName".inp", "r", stdin);
    freopen(FileName".out", "w", stdout);
#endif // Karma

    Enter();
    Solve();

    return 0;
}


Measured memory_bytes: 22528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define all(v) v.begin(), v.end()

const ll mod=1000000007;

int countBits(int in){
  int res=0;
  for(int i=0;i<10;i++){
    int msk=1<<i;
    if((in&msk)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string outputYesNo(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  string s;cin>>s;
  s[5]=' ';
  s[13]=' ';
  cout<<s<<endl;
  return 0;
}


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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define INF (1<<30)
#define INFLL (1L<<63)

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

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;

  int h, t;
  for (h = 0; h < s.size() && s[h] != 'A'; h++);
  for (t = s.size()-1; t >= 0 && s[t] != 'Z'; t--);

  cout << t - h + 1 << endl;
  return 0;
}


Measured memory_bytes: 720
#include<iostream>
using namespace std;
int main(){
  int num[5];
  int k;
  for(int i=0;i<5;i++)
    cin>>num[i];
  cin>>k;
  if(num[4]-num[0]>k)
    cout<<":("<<endl;
  else
    cout<<"Yay!"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll intceil(ll a,ll b){
    if(a>=0) return (a+b-1)/b;
    else return a/b;
}

ll intfloor(ll a,ll b){
    if(a<0) return (a-b+1)/b;
    else return a/b;
}

int main(){
    ll N,K;
    cin>>N>>K;
    vector<ll> A(N);
    rep(i,N) cin>>A[i];
    sort(all(A));

    ll ok=1e18,ng=-1e18-1;
    while(ok-ng>1){
        ll m=(ok+ng)/2;
        ll num=0;
        rep(i,N){
            if(A[i]<0){
                ll v=intceil(-m,-A[i]);
                num+=A.begin()+i-lower_bound(A.begin(),A.begin()+i,v);
            }
            else if(A[i]==0){
                if(m>=0) num+=i;
            }
            else{
                ll v=intfloor(m,A[i]);
                num+=upper_bound(A.begin(),A.begin()+i,v)-A.begin();
            }
        }
        (num>=K ? ok : ng)=m;
    }

    cout<<ok<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    int a[3100];
    int sum;
    sum = 0;
  
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
  
    for (int i = 0; i < n; ++i) {
      sum = sum + a[i];
    }
  
    cout << sum - n << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll n,a[5];
int main(){
    cin>>n>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
    ll mn=*min_element(a,a+5);
    cout<<(n+mn-1)/mn+4<<endl;
    return 0;
}


Measured memory_bytes: 256
// 2014/10/23 Tazoe

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

bool equalA(char F[1002][1002], char A[2][2], int y, int x)
{
	if(F[y][x]==A[0][0] && F[y][x+1]==A[0][1] && F[y+1][x]==A[1][0] && F[y+1][x+1]==A[1][1])
		return true;
	else
		return false;
}

int countA(char F[1002][1002], char A[2][2], int y, int x)
{
	int cnt = 0;

	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			if(equalA(F, A, y-1+i, x-1+j)){
				cnt++;
			}
		}
	}

	return cnt;
}

int main()
{
	int M, N;
	cin >> M >> N;

	char F[1002][1002];
	for(int i=0; i<=M+1; i++){
		for(int j=0; j<=N+1; j++){
			F[i][j] = 'Z';
		}
	}

	for(int i=1; i<=M; i++){
		for(int j=1; j<=N; j++){
			cin >> F[i][j];
		}
	}

	char A[2][2];
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			cin >> A[i][j];
		}
	}

	int cnt = 0;

	for(int i=1; i<=M-1; i++){
		for(int j=1; j<=N-1; j++){
			if(equalA(F, A, i, j)){
				cnt++;
			}
		}
	}

	int n_max = 0;

	for(int i=1; i<=M; i++){
		for(int j=1; j<=N; j++){
			int n_old = countA(F, A, i, j);
//			cout << n_old << endl;

			char tmp = F[i][j];

			F[i][j] = 'J';
			int n_new = countA(F, A, i, j);

			F[i][j] = 'O';
			n_new = max(n_new, countA(F, A, i, j));

			F[i][j] = 'I';
			n_new = max(n_new, countA(F, A, i, j));

			F[i][j] = tmp;

			n_max = max(n_max, n_new-n_old);
		}
	}

	cout << cnt+n_max << endl;

	return 0;
}

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

int n;
int md=1000000007;
int dp[102][5][5][5];

bool ck(int a,int b,int c,int d){
	int t[4]={a,b,c,d};

	if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
	if(t[1]==0 && t[2]==1 && t[3]==2)return(false);

	for(int cc=0;cc<3;cc++){
		swap(t[cc],t[cc+1]);
		if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
		if(t[1]==0 && t[2]==1 && t[3]==2)return(false);
		swap(t[cc],t[cc+1]);
	}

	return(true);
}

int slv(int now,int pre3,int pre2,int pre1){
	long long ret = 0ll;

	if(now==n) return(1);
	if(dp[now][pre3][pre2][pre1] != -1) return(dp[now][pre3][pre2][pre1]);

	for(int i=0;i<4;i++){
		if(ck(pre3,pre2,pre1,i)){
			ret = (ret+slv(now+1,pre2,pre1,i))%md;
		}
	}

	return(dp[now][pre3][pre2][pre1] = ret);
}

int main(){

	for(int i=0;i<102;i++){for(int j=0;j<5;j++){for(int k=0;k<5;k++){for(int l=0;l<5;l++){dp[i][j][k][l]=-1;}}}}

	cin>>n;
	int ans = slv(0,3,3,3);
	cout<<ans<<endl;

	return(0);
}

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

bool solve();

int main()
{
	if (!solve()) puts("-1");

	return 0;
}

bool solve()
{
	int N, K;
	scanf("%d%d", &N, &K);
	if ((N - 1) * (N - 2) / 2 < K) return false;
	std::vector<std::pair<int, int>> edges;
	for (int i{2}; i <= N; i++)
		edges.push_back({1, i});
	std::pair<int, int> pre(1, N);
	for (int i{(N - 1) * (N - 2) / 2 - 1}; i >= K; i--)
	{
		if (pre.second == N)
		{
			pre.first++;
			pre.second = pre.first;
		}
		pre.second++;
		edges.push_back(pre);
	}
	printf("%d\n", edges.size());
	for (auto& e: edges)
		printf("%d %d\n", e.first, e.second);
	return true;
}

Measured memory_bytes: 384
#include<stdio.h>
int cmp(const void*a,const void*b){
  return  *(int*)a-*(int*)b;
}

int main(){
  int n;
  scanf("%d",&n);
  int i,a[n];
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  qsort(a,n,sizeof(int),cmp);
  printf("%d\n",a[(n/2)]-a[(n/2)-1]);
  return 0;
}


Measured memory_bytes: 892
#####segfunc#####
def segfunc(x, y):
  return max(x,y)
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
  """
  init(init_val, ide_ele): 配列init_valで初期化 O(N)
  update(k, x): k番目の値をxに更新 O(logN)
  query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  """
  def __init__(self, init_val, segfunc, ide_ele):
    """
    init_val: 配列の初期値
    segfunc: 区間にしたい操作
    ide_ele: 単位元
    n: 要素数
    num: n以上の最小の2のべき乗
    tree: セグメント木(1-index)
    """
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
        self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
        self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  def update(self, k, x):
    """
    k番目の値をxに更新
    k: index(0-index)
    x: update value
    """
    k += self.num
    self.tree[k] = x
    while k > 1:
        self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
        k >>= 1

  def query(self, l, r):
    """
    [l, r)のsegfuncしたものを得る
    l: index(0-index)
    r: index(0-index)
    """
    res = self.ide_ele

    l += self.num
    r += self.num
    while l < r:
        if l & 1:
            res = self.segfunc(res, self.tree[l])
            l += 1
        if r & 1:
            res = self.segfunc(res, self.tree[r - 1])
        l >>= 1
        r >>= 1
    return res

def main():
  n,k = map(int, input().split())
  a = []
  for i in range(n):
    a.append(int(input()))

  array = [0] * (3 * (10 ** 5) + 1)
  seg = SegTree(array, segfunc, ide_ele)

  for i in range(len(a)):
    low = max(0, a[i] - k)
    high = min(a[i] + k + 1, 3 * (10 ** 5) + 1)
    tmp = seg.query(low, high) + 1
    
    seg.update(a[i], tmp)
    
  print(seg.query(0, 3 * (10 ** 5) + 1))
  
main()

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

S = [abs(A[0])]
for i in range(N-1):
  S.append(S[-1] + abs(A[i+1] - A[i]))
S.append(S[-1] + abs(A[N-1]))

for i in range(N):
  if i == 0:
    ans = S[N] - S[1] + abs(A[1])
    print(ans)
  elif i == N-1:
    ans = S[N-2] + abs(A[N-2])
    print(ans)
  else:
    ans = S[i-1] + (S[N] - S[i+1]) + abs(A[i+1] - A[i-1])
    print(ans)



Measured memory_bytes: 14176
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define dmp(x) cerr<<#x<<":"<<x<<endl
typedef pair<int,int> P;
typedef pair<int,P> PP; 
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;}
const int MOD = 1e9+7;
int dp[2020][2020];
signed main(){
  int n,m,p=1e9+7;
  cin>>n>>m;
  vector<int> s(n),t(m);
  for(auto &a:s)cin>>a;
  for(auto &a:t)cin>>a;
  dp[0][0]=1;
  for(int i=0;i<n;i++){
    int sum=0;
    for(int j=0;j<m;j++){
	 dp[i+1][j]+=dp[i][j];
	 dp[i+1][j]%=p;
	 sum+=dp[i][j];
	 if(s[i]==t[j]){
	   dp[i+1][j+1]+=sum;
	   dp[i+1][j+1]%=p;
	 }
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
    ans+=dp[i][m];
    ans%=p;
  }
  for(int i=0;i<=m;i++){
    ans+=dp[n][i];
    ans%=p;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 31872
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30000;
const int INF = 1000000000;
struct edge {
	int a, b, cap, flow;
};

int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];

void add_edge (int a, int b, int cap) {
	edge e1 = { a, b, cap, 0 };
	edge e2 = { b, a, 0, 0 };
	g[a].push_back ((int) e.size());
	e.push_back (e1);
	g[b].push_back ((int) e.size());
	e.push_back (e2);
}

bool bfs() {
	int qh=0, qt=0;
	q[qt++] = s;
	memset (d, -1, n * sizeof d[0]);
	d[s] = 0;
	while (qh < qt && d[t] == -1) {
		int v = q[qh++];
		for (size_t i=0; i<g[v].size(); ++i) {
			int id = g[v][i],
				to = e[id].b;
			if (d[to] == -1 && e[id].flow < e[id].cap) {
				q[qt++] = to;
				d[to] = d[v] + 1;
			}
		}
	}
	return d[t] != -1;
}

int dfs (int v, int flow) {
	if (!flow)  return 0;
	if (v == t)  return flow;
	for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
		int id = g[v][ptr[v]],
			to = e[id].b;
		if (d[to] != d[v] + 1)  continue;
		int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
		if (pushed) {
			e[id].flow += pushed;
			e[id^1].flow -= pushed;
			return pushed;
		}
	}
	return 0;
}

int dinic() {
	int flow = 0;
	for (;;) {
		if (!bfs())  break;
		memset (ptr, 0, n * sizeof ptr[0]);
		while (int pushed = dfs (s, INF))
			flow += pushed;
	}
	return flow;
}
int main()
{
	int h,w;
	cin>>h>>w;
	int base = h + w;
	for (int i = 0; i < h; ++i)
	{
		string inp;
		cin>>inp;
		for (int j = 0; j < w; ++j)
		{
			int id = i*w + j;
			add_edge(i, base + 2*id, INF);
			add_edge(h + j, base + 2*id, INF);
			add_edge(base + 2*id + 1, i, INF);
			add_edge(base + 2*id + 1, h + j, INF);
			if(inp[j] == 'o')
				add_edge(base + 2*id, base + 2*id + 1, 1);
			if(inp[j] == 'S')
			{
				s = base + 2*id;
				add_edge(base + 2*id, base + 2*id + 1, INF);
			}
			if(inp[j] == 'T')
			{
				t = base + 2*id + 1;
				add_edge(base + 2*id, base + 2*id + 1, INF);
			}
			n = base + 2*id + 1;
		}
	}
	n = MAXN - 1;
	int flow = dinic();
	if(flow == INF)
		printf("-1\n");
	else
		printf("%d\n", flow);
	return 0;
}

Measured memory_bytes: 3700
long long A,B,C,D,E,F,    I,J,K,  M,N,O,P,Q,R,S,T,U,V,  X,Y,Z;
//long long A,B,C,D,E,F,  H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;
double Aa,Bb,Cc,Dd,Ee,Ff,    Ii,Jj,Kk,  Mm,Nn,Oo,Pp,Qq,Rr,Ss,Tt,Uu,Vv,  Xx,Yy,Zz;
#include <string>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#include <cmath>

//typedef pair<long long,long long> P;
//typedef pair<long long,P> P1;
//typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
//#define INF 100000000000000000//19桁
#define INF 1e18+5//19桁
#define mod 1000000007
#define fi first
#define se second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define REP(i,n,x) for(long long i=n;i<x;i++)
#define REPN(i,n,x) for(long long i=n;i<=x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define rrep(i,x) for(long long i=x-1;i>=0;i--)
#define rrepn(i,x) for(long long i=x;i>1;i--)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()

#define ALL(v)  (v).begin(),(v).end()
//#define MAX(a,b) if(a>b)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))


const string MINUSINF = "-";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
void chmax(string &a, string b) {
    if (a == MINUSINF) a = b;
    else if (a.size() < b.size()) a = b;
    else if (a.size() == b.size()) {
        if (a < b) a = b;
    }
}


template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define pr printf
#define re return
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)


int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }

stack<long long> sta;   
queue<long long> que;
deque<long long> dque;

set <string> s_set;







long long sum,sum1,sum2,sum3,sum4;
long long flg,flg1,flg2,flg3,cnt,cnt1,cnt2,cnt3,cnt4;
long long wk,wk1,wk2,wk3,wk4;
long long ans;

bool f;

long long weight[110], value[110]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に
ll a[100010][3]; // a[i], b[i], c[i] をそれぞれまとめて a[i][0], a[i][1], a[i][2] にしてしまう
long long n,h[100005];
vector<long long> p, c;
int vis[200001];

vector<string> fi;
int Left[2100][2100], Right[2100][2100], Up[2100][2100], Down[2100][2100];

long long match[10] = {2,5,5,4,5,6,3,7,6};
vector<long long> box;



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

	long long max,max1;
	long long min,min1;

	sum=sum1=sum2=sum3=sum4=0;
	flg=flg1=flg2=flg3=cnt=cnt1=cnt2=cnt3=cnt4=0;
	max=max1=0;
	wk=wk1=wk2=wk3=wk4=0;
	ans=0;
	min=min1=INF;

	
	
	cin >> N;
	
	REPN(i,N,999){
		if(i%111==0){
			pr("%lld\n",i);
			re 0;
		}
	}
	
	return 0;
}
	

Measured memory_bytes: 4352
class Array
  def warshall_floyd
    v = size

    v.times do |k|
      v.times do |i|
        v.times do |j|
          self[i][j] = [self[i][j], self[i][k] + self[k][j]].min
        end
      end
    end
  end
end

H, W = gets.split.map(&:to_i)

cost = 10.times.map { gets.split.map(&:to_i) }
cost.warshall_floyd
wall = H.times.map { gets.split.map(&:to_i) }

ans = 0

wall.each do |row|
  row.each do |num|
    next if num == -1

    ans += cost[num][1]
  end
end

puts ans


Measured memory_bytes: 2684
#include <iostream>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    bool first = true;
    while(true) {
        int a, b;
        cin >> a >> b;
        if(!a && !b) break;
        if(!first) cout << endl;
        bool found = false;
        for(int i = a; i <= b; ++i) {
            if(i % 4 == 0) {
                if(i % 400 == 0 || i % 100 != 0) {
                    cout << i << endl;
                    found = true;
                }
            }
        }
        if(!found) cout << "NA" << endl;
        first = false;
    }
    return 0;
}

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

A = list(map(int, input().split(' ')))
ok = True
for a in A:
    if(a % 2 == 0):
        if(a % 3 != 0 and a % 5 != 0):
            ok = False

if(ok):
     print('APPROVED')
else:
    print('DENIED')


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

int main(int argc, char const *argv[])
{
	//freopen("data","r",stdin);
	int ret=0;
	int n,t;cin>>n>>t;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	for(int i=0;i<n-1;i++){
		if(v[i+1]-v[i]<t) ret+=(v[i+1]-v[i]);
		else ret+=t;
	}
	ret+=t;
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,j,n) for (int i = j; n<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e9;

int main(){
  int N,a,mini,cnt=0;cin>>N;
  vector<int> v(N),mn(N+1);
  mn[0]=INF;
  bool flg;
  cin>>v[0];
  mn[0]=v[0];
  REP(i,1,N){
    cin>>a;
    v[i]=a;
    mn[i]=min(a,mn[i-1]);
  }
  REP(i,0,N){
    if(mn[i]>=v[i])cnt++;
  }
  print(cnt)
}


Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int main(){
  int n, cnt2=0, cnt4=0;
  long long a;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a;
    if(a%2==0)cnt2++;
    if(a%4==0)cnt4++;
  }
  cnt2-=cnt4;
  n-=cnt2+cnt4;
  cout<<(cnt4>=n || (cnt2==0 && cnt4>=n-1)?"Yes":"No") << endl;
}

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

using namespace std;

long long gcd(long long a, long long b){
    return (b == 0) ? a : gcd(b, a % b);
}

int main()
{
    #ifdef DEBUG
    //freopen("input.txt", "r", stdin);
    #endif
    int n;
    cin >> n;
    long long ans = 1;
    for (int i = 0; i < n; i++){
        long long a;
        cin >> a;
        ans = (ans / gcd(a, ans)) * a;
    }
    cout << ans;
    return 0;
}


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

int main() {
    int L, N;
    vector<pair<pair<int, int>, int> > edges;

    cin >> L;

    //Find most significant bit of L
    for (int lg = 20; lg >= 0; lg--) {
        if (L & (1 << lg)) {
            N = lg;
            break;
        }
    }

    //Create graph with N + 1 vertices and 2 * N edges. Node i is connected with node i + 1 with 2 edges, each with weight 0 and 2^(i - 1)
    for (int i = 1; i <= N; i++) {
        edges.push_back({{i, i + 1}, 0});
        edges.push_back({{i, i + 1}, (1 << (i - 1))});
    }

    //For other on bits in i in L, we add an edge from vertex i + 1 to vertex N + 1 and it's weight is equal to sum of previous on bits
    int sum = (1 << N);
    for (int lg = N - 1; lg >= 0; lg--) {
        if (L & (1 << lg)) {
            edges.push_back({{lg + 1, N + 1}, sum});
            sum += (1 << lg);
        }
    }

    cout << N + 1 << " " << (int) edges.size() << endl;
    for (auto edge: edges)
        cout << edge.first.first << " " << edge.first.second << " " << edge.second << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

// Binary Index Treeは長さnの数列に対して
// 1. 区間[a,b)にxを加算する
// 2. 区間[a,b)の総和を求める
// という操作をO(log(n))で処理できる

// 区間加算にも対応したBinary Index Tree(1-indexで使うことに気をつける)
template <class Abel> struct BIT {

    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;
    
    BIT(ll n) { 
        init(n);
    }

    void init(ll n) { 
        for(ll iter = 0; iter < 2; ++iter) {
            dat[iter].assign(n+1, UNITY_SUM); 
        }
    }
    
    inline void sub_add(ll p, ll a, Abel x) {
        for(ll i = a; i < (ll)dat[p].size(); i += i & -i) {
            dat[p][i] = dat[p][i] + x;
        }
    }
    // 区間[a,b)にxを加算する(a,bは1-index)
    inline void add(ll a, ll b, Abel x) {
        sub_add(0, a, x * -(a - 1)); 
        sub_add(1, a, x);
        sub_add(0, b, x * (b - 1));
        sub_add(1, b, x * (-1));
    }
    
    inline Abel sub_sum(ll p, ll a) {
        Abel res = UNITY_SUM;
        for(ll i = a; i > 0; i -= i & -i) {
            res = res + dat[p][i];
        } 
        return res;
    }
    // 区間[a,b)の総和を計算する(a, bは1-index)
    inline Abel getsum(ll a, ll b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
};

ll ceil(ll a, ll b) {  // a÷b以上の最小の整数
    if(b == 0) {
        return 0;
    }
    return (a+b-1)/b;
}

int main() {
    ll n, d, a;
    cin >> n >> d >> a;

    vector<P> p(n);
    rep(i, n) {
        ll x, h;
        cin >> x >> h;
        p[i] = make_pair(x, h);
    }
    sort(all(p));
    
    vl x(n), h(n);
    rep(i, n) {
        x[i] = p[i].first;
        h[i] = p[i].second;
    }

    BIT<ll> biT(n+10);
    rep(i, n) {
        biT.add(i+1, i+2, h[i]);  // biT[i](iは1-index)をh[i](iは0-index)で初期化
    }

    ll ans = 0;  // 攻撃回数
    rep(idL, n) {  // idL : 攻撃範囲の左端にいるモンスターの番号(0-index)
        ll hp = biT.getsum(idL+1, idL+2);  // モンスターidLの体力を取得
        if(hp <= 0) {  // モンスターidLの体力が0以下なら
            continue;  // 次を調べる
        }
        ll cnt = ceil(hp, a);  // モンスターidLを倒すのに必要な攻撃回数
        ll idR = upper_bound(all(x), x[idL] + 2*d) - x.begin();  // 攻撃が届かないモンスターの中で最も左にいるものの番号
        biT.add(idL+1, idR+1, -a*cnt);  //   // biTの区間[idL, idR)に-a*cntを加算
        ans += cnt;  // 攻撃回数にcntを加算
    }

    out(ans);
    re0;
}

Measured memory_bytes: 9600
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=read::<String>().as_bytes().iter().map(|c|*c as char).filter(|c|*c=='o').count();
    println!("{}",a*100+700)
}


Measured memory_bytes: 4352
#include<cstdio>

int main(void){
        long long a,b;
        
        scanf("%lld%lld", &a, &b);
        long long ans = a*b;
        long long c;

     //   printf("!\n");
        if(a>b){
                c=a;
                a=b;
                b=c;
        }

       // printf("!\n");
        while(a!=0){
                c=a;
                a=b%a;
                b=c;
        }
        printf("%lld\n", ans/b);
        return 0;
}


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

const int size = 1e5 + 5;
long long dp[101][size];

int main()
{
	int n, W;
	std::cin >> n >> W;
	std::vector<int> ws(n + 1);
	std::vector<int> vs(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		std::cin >> ws[i] >> vs[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			dp[i][j] = dp[i - 1][j];
			if (ws[i] <= j)
			{
				dp[i][j] = std::max(dp[i][j], dp[i - 1][j - ws[i]] + vs[i]);
			}
		}
	}
	std::cout << dp[n][W] << '\n';
	return 0;
}

Measured memory_bytes: 81732
import numpy as np
import sys
buf = sys.stdin.buffer

N = int(input())
M = N // 2 + 1
P = np.array(input().split(),dtype = float)

dp = np.zeros([(N + 1),(N + 1)])
dp[0][0] = 1.0

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))


Measured memory_bytes: 82808
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

vector<pair<ll,ll>> v[2510];
vector<ll> dist(2510,longinf);
vector<int> used(2510,0);

void bfs(){
  queue<int> q;
  q.push(0);
  dist[0]=0;
  while(q.size()){
    int x=q.front(); q.pop();
    if(used[x]>3000){ continue; }
    for(auto e:v[x]){
      if(dist[e.F] > dist[x] + e.S){
        dist[e.F] = dist[x] + e.S;
        used[e.F]++;
        q.push(e.F);
      }
    }
  }
}

int main(){
  int n,m,p;
  cin >> n >> m >> p;
  rep(i,m){
    ll a,b,c;
    cin >> a >> b >> c; a--; b--;
    v[a].push_back({b,-c+p});
  }
  
  bfs();
  
  if(used[n-1]>1000){ 
    cout << -1 << endl; 
  } else {
    ll ans = -dist[n-1];
    if(ans<0) ans = 0;
    cout << ans << endl; 
  }
  return 0;
}


Measured memory_bytes: 3072
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;

int main(){
    int a, b; cin >> a >> b;
    if(a > 0 && b > 0){
        cout << "Positive" << endl;
    }
    else if(a < 0 && b < 0){
        if((b-a+1) % 2 == 0){
            cout << "Positive" << endl;
        }
        else{
            cout << "Negative" << endl;
        }
    }
    else{
        cout << "Zero" << endl;
    }
    return 0;
}

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

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

Measured memory_bytes: 256
ans = -10 ** 9
A = [0] * 10


def func():
    if sum(A) == 0:
        return
    score = 0
    for i in range(N):
        days = sum([a * f for a, f in zip(A, F[i])])
        score += P[i][days]
    global ans
    ans = max(ans, score)


def dfs(pos):
    if pos == 10:
        func()
        return
    A[pos] = 0
    dfs(pos + 1)
    A[pos] = 1
    dfs(pos + 1)


N = int(input())

F = []
for i in range(N):
    F.append(list(map(int, input().split())))
P = []
for i in range(N):
    P.append(list(map(int, input().split())))

dfs(0)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
char sym(bool op) {
    return op ? '+' : '-';
}
int sgn(bool op) {
    return op ? 1 : -1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string abcd;
    cin >> abcd;
    int a = abcd[0] - '0';
    int b = abcd[1] - '0';
    int c = abcd[2] - '0';
    int d = abcd[3] - '0';
    for(bool op1 : {true, false}) {
        for(bool op2 : {true, false}) {
            for(bool op3 : {true, false}) {
                int res = a + sgn(op1) * b + sgn(op2) * c + sgn(op3) * d;
                if(res == 7) {
                    cout << a << sym(op1) << b << sym(op2) << c << sym(op3) << d << "=7" << endl;
                    return 0;
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    int n;
    double a, b, c, d, e, f;
    double x1, x2, x3, y1, y2, y3, px, py, r;
    cin >> n;
    while (n--) {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        a = 2 * (x1 - x2);
        b = 2 * (y1 - y2);
        c = x1*x1 + y1*y1 - x2*x2 - y2*y2;
        d = 2 * (x1 - x3);
        e = 2 * (y1 - y3);
        f = x1*x1 + y1*y1 - x3*x3 - y3*y3;
        px = (c*e - b*f) / (a*e - b*d);
        py = (c*d - a*f) / (b*d - a*e);
        r = sqrt((px - x1)*(px - x1) + (py - y1)*(py - y1));
        printf("%.3f %.3f %.3f\n", px, py, r);
    }
    
    return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
using namespace std;
typedef pair<int, int> P;

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

typedef long long ll;
typedef vector<int> VI;



int partition(pair<string, int> (&A)[100010], int p, int r){
    int x = A[r].second; // A中の最後の要素
    int i = p-1;
    for(int j=p; j<r; ++j){
        if(A[j].second<=x){ // A[j]よりxが大きい=A[j]はA[r]より小さい
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}

void quicksort(pair<string, int> (&A)[100010], int p, int r){
    int q;
    if(p<r){
        q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }
}
int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n; cin >> n;
    pair<string, int>A[100010];
    
    REP(i, n) {
        string s; int a; cin >> s >> a;
        A[i] = make_pair(s, a);
    }
    map<int, string> m1, m2;
    for(int i=0; i<n; ++i) m1[A[i].second]+=A[i].first;
    quicksort(A, 0, n-1);
    for(int i=0; i<n; ++i) m2[A[i].second]+=A[i].first;
    
    bool f = true;
    for(int i=0; i<n; ++i){
        if(m1[A[i].second]!=m2[A[i].second]) f=false;
    }
    if(f) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
    for(int i=0; i<n; ++i){
        cout << A[i].first << " " << A[i].second << endl;
    }
	return 0;
}


Measured memory_bytes: 14736
n = int(input())
x = list(map(int,input().split()))
m = int(input())
a = list(map(int,input().split()))

x.insert(0,0)
a.insert(0,0)

for i in range(1,m+1):
    if x[a[i]] == 2019:
        pass
    elif a[i] == n:
        x[a[i]] = x[a[i]]+1
    elif x[a[i]]+1 != x[a[i]+1]:
        x[a[i]] = x[a[i]]+1


x.pop(0)
print(*x,sep = '\n')



Measured memory_bytes: 5608
#!/usr/bin/python

# AtCoder Beginner Contest 075
# D - Axis-Parallel Rectangle

from sys import stdin

def nPointsInRect(y0, y1, points):
  return len([p for p in points if y0 <= p[1] <= y1])

def solve(K, points):
  points.sort()  # sort the points by x-coordinates
  xs = [p[0] for p in points]          # sorted x-coordinates
  ys = sorted([p[1] for p in points])  # sorted y-coordinates
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  # the biggest rect
  for i0 in range(len(points)):
    for i1 in range(i0 + K - 1, len(points)):
      for j in range(len(ys)):
        y0 = ys[j]
        for y1 in ys[j + K - 1:]:
          if nPointsInRect(y0, y1, points[i0 : i1 + 1]) >= K:
            area = (xs[i1] - xs[i0]) * (y1 - y0)
            minArea = min(minArea, area)
            break  # no other rects for the same i0, i1, y0 are unnecessary
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))

Measured memory_bytes: 3064
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
ans = (10**9, -1)
for i in range(N):
    tmp = T - 0.006 * H[i]
    if abs(tmp - A) < ans[0]:
        ans = (abs(tmp - A), i + 1)
print(ans[1])


Measured memory_bytes: 62636
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int MAXN = 1010;
const int INF = 2e9;
const int mod = 1e9 + 7;

int n,m,sum,cnt;
int a[MAXN];

signed main () {
	cin >> n >> m;
	for(register int i = 1;i <= n; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	for(register int i = 1;i <= n; ++i) 
		if(a[i] * 4 * m >= sum) cnt++;
	puts(cnt >= m ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NON -1

int M[N][N];
int n;

int prim();

int main(){
  int i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&M[i][j]);
      if(M[i][j]==NON) M[i][j]=INFTY;
    }
  }

  printf("%d\n",prim());
  
  return 0;
}

int prim(){
  int u,min,sum=0;
  int i;
  int color[N],d[N],p[N];

  //初期化
  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=NON;
    color[i]=WHITE;
  }
  
  d[0]=0;

  while(1){
    min=INFTY;
    u=NON;
    //進路決め
    for(i=0;i<n;i++){
      if(min>d[i] && color[i]!=BLACK){
	u=i;
	min=d[i];
      }
    }
    if(u==NON) break;
    color[u]=BLACK;
    //次の節点の設定
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && M[u][i]!=INFTY)
      if(d[i]>M[u][i]){
	d[i]=M[u][i];
	p[i]=u;
	color[i]=GRAY;
      }
    }
  }
  for(i=0;i<n;i++){
    if(p[i]!=NON) sum+=M[i][p[i]];
  }
  
  return sum;
}



Measured memory_bytes: 2104
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> N;
	vector<int>v(N);
	for (auto &i : v) {
		cin >> i;
		i++;
	}
	vector<int>sum(N + 10);
	long long int ans = 1;
	sum[0] = 3;
	for (auto i : v) {
		ans *= (sum[i - 1] - sum[i]);
		ans %= MOD;
		//cout << ans << endl;
		sum[i]++;
	}
	cout << ans << endl;
}


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

#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 2e5 + 10;

int A[N], n;
long long S[N];

long long sum(int l, int r) {
	return S[r] - S[l - 1];
}

int main() {

	scanf("%d", &n);
	For(i, 1, n) scanf("%d", &A[i]), S[i] += S[i - 1] + A[i];

	int p = 1, q = 3;
	long long ans = 1e18;
	For(i, 2, n - 2) {
		while (p < i - 1 && abs(sum(1, p) - sum(p + 1, i)) > abs(sum(1, p + 1) - sum(p + 2, i))) ++p;
		while (q < n - 1 && abs(sum(i + 1, q) - sum(q + 1, n)) > abs(sum(i + 1, q + 1) - sum(q + 2, n))) ++q;
		long long val[4] = {sum(1, p), sum(p + 1, i), sum(i + 1, q), sum(q + 1, n)};
		sort(val, val + 4);
		ans = min(ans, val[3] - val[0]);
	}
	printf("%lld\n", ans);

	return 0;
}

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

using namespace std;

int main()
{
  string A, B; cin >> A >> B;
  if (A.size() > B.size()) {
    cout << "GREATER";
  } else if (A.size() < B.size()) {
    cout << "LESS";
  } else {
    if (A > B) cout << "GREATER";
    else if (A < B) cout << "LESS";
    else cout << "EQUAL";
  }
}

Measured memory_bytes: 256