akhauriyash/Code-Regression huggingface dataset:
package main

// Solution for https://atcoder.jp/contests/abc074/tasks/arc083_a

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var a, b, c, d, e, f int
	con.Scan(&a, &b, &c, &d, &e, &f)
	maxX, maxY := a, 0
	for i := 0; ; i++ {
		x := a * i
		if 100*x > f {
			break
		}
		for j := 0; ; j++ {
			x := x + b*j
			if 100*x > f {
				break
			}
			for k := 0; ; k++ {
				y := c * k
				if 100*x+y > f {
					break
				}
				for l := 0; ; l++ {
					y := y + d*l
					if 100*x+y > f {
						break
					}
					if y > x*e {
						break
					}
					if y*(maxX+maxY) > maxY*(x+y) {
						maxX = x
						maxY = y
					}
				}
			}
		}
	}
	con.Println(100*maxX+maxY, maxY)
	return nil
}


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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int,bool>>> a(n);
    for (int i = 0;i < n;++i) {
        int b;
        cin >> b;
        for (int j = 0;j < b;++j) {
            int x,y;
            cin >> x >> y;
            x--;
            a[i].push_back(make_pair(x,y));
        }
    }
    int ans = 0;
    for (int s = 0;s < (1<<n);++s) {
        bool ok = true;
        for (int i = 0;i < n;++i) if ((s>>i)&1) {
            for (pair<int,bool>& p : a[i]) {
                if (p.second) {
                    if (((s>>p.first)&1)^1) ok = false;
                } else {
                    if ((s>>p.first)&1) ok = false;
                }
            }
        }
        if (ok) {
            int cnt = 0;
            for (int i = 0;i < n;++i) if ((s>>i)&1) cnt++;
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll>P;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void SAY(bool YES){cout<<(YES?"YES":"NO")<<endl;};
void Say(bool Yes){cout<<(Yes?"Yes":"No")<<endl;};

const ll MOD = 1000000007;

int main(){

    ll W, a, b;
    cin >> W >> a >> b;
    if(abs(a - b) <= W)cout << 0 << endl;
    else cout << abs(a - b) - W << endl;


    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<vector>
int w,h,fld[64][64];

void dfs(int y,int x){
    if(x<0||x>=w||y<0||y>=h)return;
    if(!fld[y][x])return;
    fld[y][x]=0;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            if(i||j)dfs(y+i,x+j);
        }
    }
}
int main(){
    while(scanf("%d%d",&w,&h),w||h){
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                scanf("%d",&fld[i][j]);
            }
        }

        int cnt=0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(fld[i][j]){
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

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

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

	int n;
	cin >> n;
	int a[n+2], subete = 0;
	a[0] = 0;
	a[n+1] = 0;
	FOR(i, 1, n+1){
		cin >> a[i];
		subete += abs(a[i] - a[i-1]);
	}
	subete += abs(a[n]);
	int resu;
	FOR(i, 1, n+1){
		resu = subete;
		if ((a[i-1] <= a[i] && a[i] <= a[i+1]) || (a[i-1] >= a[i] && a[i] >= a[i+1])){
			cout << subete << "\n";
			continue;
		}
		resu -= abs(a[i] - a[i-1]) + abs(a[i+1] - a[i]);
		resu += abs(a[i+1] - a[i-1]);
		cout << resu << "\n";
	}
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

signed main(){
	int N, K;
	cin >> N >> K;
	if (K == 0) {
		cout << N * N << endl;
		return 0;
	}
	int res = 0;
	for(int b = K + 1; b <= N; ++b) {
		res += (N+1) / b * (b - K);
		res += max((N + 1) % b - K, 0LL);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
string normal = "-";
void stchange(string &a, string b) {
	if (a == normal)a = b;
	else if (a.size() < b.size())a = b;
	else if (a.size() == b.size()) {
		if (a < b)a = b;
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	vector<int>A(M);
	for (int i = 0; i < M; ++i)cin >> A[i];
	int list[10] = { 0,2,5,5,4,5,6,3,7,6 };
	string dp[10100];//dp[i]でi本のマッチ棒を使って作れる文字列の最大値
	for (int i = 0; i < 1010; ++i)dp[i] = normal;
	dp[0] = "";
	for (int i = 0; i <=N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (dp[i] == normal)continue;
			for (int j = 0; j < M; ++j) {
				stchange(dp[i + list[A[j]]], dp[i] + (char)('0' + A[j]));
			}
		}
	}
	cout << dp[N] << endl;
	return 0;
}



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

end_index = 0
sum_plus = A[0]
sum_xor = A[0]
ans = 0

for i in range(N):
    if(i > 0):
        sum_plus -= A[i-1]
        sum_xor ^= A[i-1]
    if(i == N-1):
        ans += 1
        break

    while(sum_plus == sum_xor and end_index < N):
        end_index += 1
        if(end_index == N):
            break
        sum_plus += A[end_index]
        sum_xor ^= A[end_index]

    if(end_index == N):
        end_index -= 1
    else:
        sum_plus -= A[end_index]
        sum_xor ^= A[end_index]
        end_index -= 1

    ans += end_index - i + 1
    
print(ans)


Measured memory_bytes: 24584
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    long long N, T;
    cin >> N >> T;
    vector<long long> t(N);
    for(int i = 0; i < N; i++){
        cin >> t[i];
    }

    long long X = 0;
    for(int i = 1; i < N; i++){
        if(t[i] - t[i-1] <= T){
            X = X + t[i] - t[i-1];
        }else{
            X = X + T;
        }
    }
    X += T;

    cout << X << endl;


    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int r = 0,b = 0;
	string s;
	cin>>s;
	int sum = 0;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '1'){
			if(r!=0){
				r--;
				sum+=2; 
			}
			else
				b++;
		}
		else if(s[i] == '0'){
			if(b!=0){
				b--;
				sum+=2;
			}
			else
				r++;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 512
from itertools import *
g=lambda a,x,b:a+b if x=='+'else a-b if x=='-'else a*b
def f(s):
 for a,b,c,d in permutations(s):
  for x,y,z in product('*+-',repeat=3):
   if g(g(a,x,b),y,g(c,z,d))==10:return f"(({a} {x} {b}) {y} ({c} {z} {d}))"
   if g(g(a,x,g(b,y,c)),z,d)==10:return f"(({a} {x} ({b} {y} {c})) {z} {d})"
 return 0
for e in iter(input,'0 0 0 0'):print(f(list(map(int,e.split()))))


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

namespace Sample101
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] S = Console.ReadLine().ToArray();
            bool[] letters = Enumerable.Repeat<bool>(false, 26).ToArray();

            for (int i = 0; i < S.Length; ++i)
            {
                letters[(int)S[i] - (int)'a'] = true;
            }

            string result = "None";
            for (int i = 0; i < letters.Length; ++i)
            {
                if (letters[i] == false)
                {
                    result = ((char)((int)'a' + i)).ToString();
                    break;
                }
            }

            Console.WriteLine(result);
        }
    }
}

Measured memory_bytes: 14176
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    
	    int n = Integer.parseInt(sc.next());
	    int k = Integer.parseInt(sc.next());
	    
	    if (n<2 || n>100000) {
	    	System.out.println("Entrada invalida!!!");
	    	System.exit(0);
	    }
	    
	    if (k<1 || k>100) {
	    	System.out.println("Entrada invalida!!!");
	    	System.exit(0);
	    }
	    
	    int[] altura = new int[n];
	    int[] custo = new int[n];
	    
	    Arrays.fill(custo, Integer.MAX_VALUE);
	    custo[0] = 0;
	    
	    for(int i = 0; i < n; i++) altura[i] = Integer.parseInt(sc.next());
	    
	    for(int i = 0; i < n; i++) {
	      for(int j = 1; j <= k && i + j < n; j++) {
	        custo[i+j] = Math.min(custo[i+j], custo[i] + Math.abs(altura[i+j] - altura[i]));
	      }
	    }
	    
	    System.out.println(custo[n-1]);
	  }


}


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

using namespace std;

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

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(pi c, pi d){
	return c.S < d.S;
}

int main() {
	ll N, M;
	string s, t;
	cin >> N >> M >> s >> t;
	ll g = __gcd(N, M);
	ll n = N/g;
	ll m = M/g;
	REP(i, 0, g){
		if(s[i*n] != t[i*m]){
			cout << -1;
			return 0;
		}
	}
	cout << (N*M)/g;

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
vector <long long> a[100005];

int main()
{
	long long n,m,x,y,ans = 0;
	priority_queue <long long> b;
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		cin >> x >> y;
		a[x].push_back(y);
	}
	
	for(int i = 1;i <= m;i++){
		for(int j = 0;j < a[i].size();j++){
			b.push(a[i][j]);
		}
		if(!b.empty()){
			ans += b.top();
			b.pop();
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5632
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;

class RMQ{
  int n;
  vector<pii> dat;
public:
  RMQ(int n_){
    init(n_);
  }
  void init(int n_);
  void update(int k, int a);
  pii query(int a, int b, int k = 0, int l = 0, int r = 0);
};
void RMQ::init(int n_){
  n = 1;
  while(n < n_)n *= 2;
  dat.resize(2*n - 1);
  for (int i = 0; i < 2*n - 1; i++) {
    if(i < n - 1) dat[i] = mp(-1e9, -1e9);
    else dat[i] = mp(0, -i + n - 1);
  }
}

void RMQ::update(int k, int a){
  k += n - 1;
  dat[k].first += a;
  while(k > 0){
    k = (k - 1)/2;
    dat[k] = max(dat[2*k + 1], dat[2*k + 2]);
  }
}

pii RMQ::query(int a, int b, int k, int l, int r){
  if(r <= l)r = n;
  if(r <= a || b <= l)return mp(-1e9, -1e9);
  if(a <= l && r <= b)return dat[k];
  pii vl = query(a, b, 2*k + 1, l, (r + l)/2);
  pii vr = query(a, b, 2*k + 2, (r + l)/2, r);
  return max(vl, vr);
}
int main(int argc, char *argv[]){
  int n, p, a, v;
  cin >> n >> p;
  RMQ segtree(n);
  for (int i = 0; i < p; i++) {
    scanf("%d %d", &a, &v);
    segtree.update(a - 1, v);
    pii ans = segtree.query(0, n);
    printf("%d %d\n", -ans.second + 1, ans.first);
  }

  return 0;
}

Measured memory_bytes: 17428
#include<stdio.h>
int main(void)
{
	int i;
	int N;
	int A[100];
	int max=0;
	int counter=0;
	
	scanf("%d",&N);//Nの値を取得
	
	for(i=0;i<N;i++)
	{
		scanf("%d",&A[i]);//A[i]の値を取得
		

		if(A[i]==1)
			counter++;
		else
		{
			if(max<counter)
				max=counter;
			counter=0;
		}
	}
	if(max<counter)
		max=counter;
	printf("%d\n",max+1);
	return(0);
}


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

int main() {
  string c;
  cin >>  c;
  
  if ( c == "a" || c == "e" || c == "i" || c == "o" || c == "u" ) {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	int N, K, T, U, V, L; cin >> N >> K >> T >> U >> V >> L;
	vector<ld>ds;
	int pre = 0;
	for (int i = 0; i < N; ++i) {
		int d; cin >> d;
		ds.push_back(d-pre);
		pre = d;
	}
	ds.push_back(L - pre);
	ld max_dash = (K + 1)*T;

	ld now_dash = 0;
	ld ans = 0;
	for (int i = 0; i < ds.size(); ++i) {
		if (now_dash*V > ds[i]) {
			now_dash -= ds[i] / V;
			ans += ds[i] / V;
		}
		else {
			ans += now_dash + (ds[i] - now_dash*V) / U;
			now_dash = 0;
		}
		now_dash = min(now_dash + T, max_dash);
	}
	cout << setprecision(22)<<fixed<<ans << endl;
	return 0;
}

Measured memory_bytes: 3280
using System;
using System.Collections.Generic;
using System.Linq;

namespace _0030
{
    class Program
    {

        static int trinum;
        static int einum;
        static int tyonum;
        static int donum;

        static bool IsTriangle(int a, int b, int c)
        {

            if(a + b > c && a + c > b && b + c > a)
            {
                return true;
            }
            else
            {
                return false;
            }
        }


        static void TriangleType(int a, int b, int c)
        {
            int[] list = { a, b, c };

            Array.Sort(list);

            a = list[0];
            b = list[1];
            c = list[2];

            int u = a * a + b * b - c * c;

            if(u < 0)
            {
                donum++;
            }
            else if(u > 0)
            {
                einum++;
            }
            else
            {
                tyonum++;
            }
        }

        
        static void Main(string[] args)
        {

            trinum = 0;
            einum = 0;
            tyonum = 0;
            donum = 0;

            do
            {
                string[] str = Console.ReadLine().Split(' ');

                int a = int.Parse(str[0]);
                int b = int.Parse(str[1]);
                int c = int.Parse(str[2]);

                if(!IsTriangle(a, b, c))
                {
                    break;
                }

                trinum++;

                TriangleType(a, b, c);

            } while (true);

            Console.WriteLine($"{trinum} {tyonum} {einum} {donum}");

            
        }
    }
}


Measured memory_bytes: 18052
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
#define ll long long int
const double mx = 2e6 + 5 ;

void solve()
{
	int n, k;
	cin>>n>>k;
	vector<int> vect(n);
	REP(i, n)
		cin>>vect[i];
	sort(all(vect));
	ll ans = 0;
	for(int i=0; i<k; i++)
	{
		ans+=vect[i];
	}
	cout<<ans<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; i--)
#define REP(i, k, n) for(int i=(int)(k); i<(int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define PQ(T) priority_queue<T>
#define PQS(T) priority_queue<T, vector<T>, greater<T> >
#define deci cout << fixed << setprecision(15);
typedef long long ll;
const int INF = INT_MAX;
const ll inf = 1e18;
const ll mod = 998244353;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x, ll y){ if(x>y) swap(x, y);while(x!=0){ y%=x; swap(x, y); }return y; }
ll mpow(ll x, ll r){if(r==0) return 1;if(r%2==1){ return x*mpow(x, r-1)%mod; }else{ ll aa = mpow(x, r/2); return aa*aa%mod; }}

int N, a[200010];
vector<int> G[200010];
P ind[200010];
int ans[200010];
vector<ll> dp(200010);

void dfs(int v, int p){
	int nn = lower_bound(all(dp), a[v]) - dp.begin();
	ind[v].first = nn;
	ind[v].second = dp[nn];
	dp[nn] = a[v];
	ans[v] = lower_bound(all(dp), inf) - dp.begin();
	rep(i, G[v].size()){
		if(G[v][i] == p) continue;
		dfs(G[v][i], v);
	}
	dp[ind[v].first] = ind[v].second;
	return;
}

int main(){
	cin >> N;
	rep(i, N) cin >> a[i];
	rep(i, N-1){
		int u, v; cin >> u >> v;
		u--; v--;
		G[u].pb(v);
		G[v].pb(u);
	}
	rep(i, 200010) dp[i] = inf;
	dfs(0, -1);
	rep(i, N) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 31952
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    long long int a, b;
    cin >> a >> b;
    if(a*b <= 0)
        cout << "Zero" << endl;
    else if(a > 0 and b > 0)
        cout << "Positive" << endl;
    else {
        if(abs(a-b) % 2 == 0)
            cout << "Negative" << endl;
        else
            cout << "Positive" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
S=str(input())
cnt=0
maxcnt=0
for i in S:
    if(i=="A" or i=="C" or i=="G" or i=="T"):
        cnt+=1
    else:
        if(maxcnt<cnt):
            maxcnt=cnt
        cnt=0
if(maxcnt<cnt):
    maxcnt=cnt
print(maxcnt)

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

using namespace std;

int main() {
  int R,G,B,N;

  cin >> R >> G >> B >> N;

  int count = 0;

  for(int r=0; r<=N; r++){
    int sum1 = 0;
    sum1 += R*r;
    if(sum1 < N){
      for(int g=0; g<=N; g++){
        int sum2 = sum1 + G*g;
        if(sum2 < N){
          if((N-sum2)%B == 0){
            count++;
          }
        }else if(sum2 == N){
          count++;
          break;
        }else if(sum2 > N){
          break;
        }
      }
    }else if(sum1 == N){
      count++;
      break;
    }else if(sum1 > N){
      break;
    }
  }

  cout << count;


  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

template<class T> struct UnionFindDiff {
    int n;
    vector<int> U;
    vector<T> D; // P[U[x]] - P[x]
    UnionFindDiff() {}
    UnionFindDiff(int n_): n(n_), U(n, -1), D(n, T(0)) {}
    int root(int x) {
	if (U[x] < 0) return x;
	int r = root(U[x]);
	if (U[x] != r) {
	    D[x] = D[U[x]] + D[x];
	    U[x] = r;
	}
	return r;
    }
    int link(int x, int y, T diff /* = P[x] - P[y] */) {
	int p, q;
	p = root(x); q = root(y);
	if (p == q) return p;
	if (U[q] < U[p]) { swap(p, q); swap(x, y); diff = -diff; }
	D[q] = D[x] - D[y] + diff;
	U[p] += U[q];
	n--;
	return U[q] = p;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -U[root(x)]; }
    int count() { return n; }
    T diff(int x, int y) { // return P[x] - P[y];
	root(x); root(y);
	// assert(root(x) == root(y));
	return D[y] - D[x];
    }
};
int N, R, C;
VI B[200011];
const LL INF = 1LL<<60;

void MAIN() {
    scanf("%d%d%d", &R, &C, &N);
    UnionFindDiff<LL> U(R+C);

    bool yes = true;
    REP (i, N) {
	int r, c, a;
	scanf("%d%d%d", &r, &c, &a);
	r--; c--;
	c += R;
	if (U.same(r, c)) {
	    LL d = U.diff(r, c);
	    if (d != a) yes = false;
	} else {
	    U.link(r, c, a);
	}
    }

    if (yes) {
	REP (i, R+C) if (U.size(i) > 1) B[U.root(i)].push_back(i);
	REP (i, R+C) if (!B[i].empty()) {
	    LL rmi = INF, cma = -INF;
	    EACH (e, B[i]) {
		if (*e < R) {
		    amin(rmi, U.diff(*e, i));
		} else {
		    amax(cma, U.diff(*e, i));
		}
	    }

	    if (rmi - cma < 0) yes = false;
	}
    }
    puts(yes? "Yes": "No");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 10368
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Object o = run();
        if (o != null)
            System.out.println(o);
    }

    static Object run() {
        try (Scanner sc = new Scanner(System.in)) {
            int n = sc.nextInt();
            ArrayList<Integer> a = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                a.add(sc.nextInt());
            }
            long latest = 0;
            long result = 0;
            for (int i = 0; i < n; i++) {
                if (latest > a.get(i)) {
                    result += latest - a.get(i);
                } else {
                    latest = a.get(i);
                }
            }
            return result;
        }
    }
}

class ChenNumberUtil {
    static Collection<Integer> getDivisors(int n) {
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                al.add(i);
                if (n / i != i)
                    al.add(n / i);
            }
        }
        Collections.sort(al);
        return al;
    }
}

class ChenBitUtil {
    static int popCount(int bit) {
        return Integer.bitCount(bit);
    }

    static boolean isFlag(int bit, int i) {
        return 0 != (bit & (1 << i));
    }

    static int setTrue(int bit, int i) {
        return bit |= (1 << i);
    }

    static int setFalse(int bit, int i) {
        return bit &= ~(1 << i);
    }

    static int setReverse(int bit, int i) {
        return isFlag(bit, i) ? setFalse(bit, i) : setTrue(bit, i);
    }

    static int reverseAll(int bit) {
        return ~bit;
    }
}


Measured memory_bytes: 55444
def test():

	n = int(input())
	A = list(map(int,input().split()))

	swap_count = 0
	for i in range(n):
		mini = i
		for j in range(i,n):
			if A[j] < A[mini]:
				mini = j
		tmp = A[i]
		A[i] = A[mini]
		A[mini] = tmp
		if i != mini:
			swap_count += 1

	for i in range(n-1):
		print(f"{A[i]} ",end = '')
	print(f"{A[n-1]}")
	print(swap_count)


if __name__ == "__main__":
	test()


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

int main(){
	string N;
	cin >> N;
	char ch =  N[N.length()-1] ;
	if (ch == '2' || ch == '4' || ch == '5' || ch == '7' || ch == '9') {
		cout << "hon" << endl;
	} else if (ch == '0' || ch == '1' || ch == '6' || ch == '8') {
		cout << "pon" << endl;
	} else {
		cout << "bon" << endl;
	}
}

Measured memory_bytes: 3588
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
	int n, k, b, ans = 0;
	vi l;
	cin >> n >> k;
	rep(i, n) {
		cin >> b;
		l.pb(b);
	}
	sort(l.rbegin(), l.rend());
	rep(i, k) {
		ans += l[i];
	}
	cout << ans;
	return 0;
}

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

typedef unsigned long long ll;
const int maxn = 1005;
int n, k, idx = 0;
ll res = 0;
ll prefix[maxn], a[maxn];
vector<ll> interval;
vector<ll> bitmap[70];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	prefix[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		prefix[i] = prefix[i-1] + a[i];
	}
	for (int i = 0; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			interval.push_back(prefix[j]-prefix[i]);
		}
	}
	for (ll x : interval) {
		for (int i = 0; i < 64; ++i) {
			if (((ll(1)<<i)&x) != 0)
				bitmap[i].push_back(x);
		}
	}
	for (int i = 63; i >= 0; i--) {
		if (bitmap[i].size() >= k) {
			idx = i;
			break;
		}
	}
	map<ll, int> tree;
	for (ll x : bitmap[idx]) {
		if (tree[x] == 0) tree[x] = 1;
		else tree[x] += 1;
	}

	for (int i = idx; i >= 0; i--) {
		int cnt = 0;
		for (auto p : tree) {
			ll x = p.first; int num = p.second;
			if (((ll(1)<<i)&x) != 0) {
				cnt += num;
			}
		}
		if (cnt >= k) {
			res |= (ll(1)<<i);
			for (auto p : tree) {
				ll x = p.first; int num = p.second;
				if (((ll(1)<<i)&x) == 0) {
					tree[x] = 0;
				}
			}
		}
	}

	cout << res << endl;
}

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

int main()
{
   char s;
   cin >> s;

   if (isupper(s))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }

   return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int MAX=1e9;
int MOD=1e9+7;


int main(){
  int n,m;cin>>n>>m;
  int ans=0;
  int cnt[m];for(int i=0;i<m;i++)cnt[i]=0;
  if(n==1){
    int k;cin>>k;
    ans=k;
    for(int j=0;j<k;j++){
      int a[k];cin>>a[j];
      cnt[a[j]]++;
    }
  }else{
    for(int i=0;i<n;i++){
      int k;cin>>k;
      for(int j=0;j<k;j++){
        int a[k];cin>>a[j];
        cnt[a[j]-1]++;
      }
    }
    for(int i=0;i<m;i++){
      if(cnt[i]==n)ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
N,Y=input().split()
n=int(N)
y=int(Y)//1000
p=y-n
s=y//10
t=y//5
i=-1
j=-1
k=-1
fl=False
for X in range(0,s+1):
    for Y in range(0,t+1):
        q=p-(9*X+4*Y)
        if q==0 and X+Y<=n:
            Z=n-X-Y
            i=X
            j=Y
            k=Z
            break
        if fl:
            break
    if fl:
        break
print(i,j,k)
        

Measured memory_bytes: 3188
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <cmath>

using namespace std;

typedef long long ll;

ll L, n, X[400010], LS[400010], LSS[400010], RS[400010], RSS[400010];

ll getL(ll x, ll y) {
    if(y >= x) return LS[x];
    return LS[x] - LS[x - y];
}

ll getR(ll x, ll y) {
    if(y >= x) return RS[n - x + 1];
    return RS[n - x + 1] - RS[n - x + 1 + y];
}

int main() {
    scanf("%lld%lld", &L, &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &X[i]), LS[i] = LS[i - 1] + X[i];
    for(int i = n; i >= 1; i--) RS[i] = RS[i + 1] + (L - X[i]);
    ll ans = 0;
    for(int i = 0; i <= n; i++) {
        int a = i, b = n - i;
        if(a > b) ans = max(ans, (getL(a, b + 1) + getR(b, b)) * 2 - X[i]), ans = max(ans, (getL(a, b) + getR(b, b)) * 2 - (L - X[i + 1]));
        else ans = max(ans, (getL(a, a) + getR(b, a)) * 2 - (L - X[i + 1]));
    }
    for(int i = 1; i <= n; i++) X[i] = L - X[i];
    reverse(X + 1, X + n + 1);
    for(int i = 1; i <= n; i++) LS[i] = LS[i - 1] + X[i];
    for(int i = n; i >= 1; i--) RS[i] = RS[i + 1] + (L - X[i]);
    for(int i = 0; i <= n; i++) {
        int a = i, b = n - i;
        if(a > b) ans = max(ans, (getL(a, b + 1) + getR(b, b)) * 2 - X[i]), ans = max(ans, (getL(a, b) + getR(b, b)) * 2 - (L - X[i + 1]));
        else ans = max(ans, (getL(a, a) + getR(b, a)) * 2 - (L - X[i + 1]));
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 10496
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String[] str = new String[9];
		int[][] a = new int[2][9];
		int[][] sum = new int[2][9];
		for(int i = 0; i < 9; i++){
			str[i] = cin.next();
			a[0][i]=cin.nextInt();
			a[1][i]=cin.nextInt();
			sum[0][i]=a[0][i] + a[1][i];
			sum[1][i]=a[0][i]*200 + a[1][i]*300;
		}
		int cnt=0;
		for(int i = 1; i < 4;i++){
			for(int j = 0; j < 3;j++){
				System.out.print(str[cnt]+" ");
				System.out.println(sum[0][cnt] + " " + sum[1][cnt++]);
			}
		}
	}

}

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

using namespace std;

#define int long long
long long pw[15], sum, cur = 0, pw1[15];

signed main() {
    cin.tie(0), ios::sync_with_stdio(0);
    pw[0] = 1;
    for(int i = 1; i <= 9; i++){
        pw[i] = pw[i - 1] * 10;
    }
    int num = -1;
    for(int i = 9; i >= 0; i--){
        cout << "? " << pw[i] << "\n";
        cout.flush();
        char c;
        cin >> c;
        if(c == 'Y'){
            num = i + 1;
            break;
        }
    }
    if(num == 10){
        for(int i = 9; i >= 0; i--){
            if(i == 0){
                cout << "! " << pw[i] << "\n";
                cout.flush();
                exit(0);
            }
            cout << "? " << pw[i] - 1 << "\n";
            cout.flush();
            char c;
            cin >> c;
            if(c == 'N'){
                cout << "! " << pw[i] << "\n";
                cout.flush();
                exit(0);
            }
        }
    }
    for(int i = 1; i <= num; i++){
        int l = 0, r = 9, mid;
        if(i == 1)
            l = 1;
        if(i < num){
            while(l < r){
                mid = (l + r + 1) >> 1;
                sum = cur * 10 + mid;
                cout << "? " << sum << "\n";
                cout.flush();
                char c;
                cin >> c;
                if(c == 'Y')
                    l = mid;
                else
                    r = mid - 1;
            }
            cur = cur * 10 + l;
        }
        else{
            for(int j = l; j <= r; j++){
                int sum = cur * 10 + j;
                if(i == num)
                sum = sum * 10 + 9;
                cout << "? " << sum << "\n";
                cout.flush();
                char c;
                cin >> c;
                if(c == 'Y'){
                    cur = cur * 10 + j;
                    break;
                }
            }
        }
    }
    cout << "! " << cur << "\n";
    cout.flush();
    exit(0);
}

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

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/

  int a[7],b[7];

  for(int i=0;i<7;i++){
    cin>>a[i]>>b[i];

    cout<<abs(a[i]-b[i])<<endl;

  }

  return 0;

}



Measured memory_bytes: 3176
#include <stdio.h>
int main()
{
  int a,b;
  char op;
  for(;;){
    scanf("%d %c %d",&a,&op,&b);
    if(op =='+') printf("%d\n",a+b);
    else if(op =='-') printf("%d\n",a-b); 
    else if(op =='*') printf("%d\n",a*b);
    else if(op == '/') printf("%d\n",a/b);
    else if(op == '?')  break;
  }

  
  

  return 0;
}

Measured memory_bytes: 600
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/05/06 07:32:23 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

using namespace std;

#define	int	long long
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

typedef long long 			ll;
typedef vector<int>			VI;
typedef vector<vector<int>>	VVI;
typedef pair<int, int>		PII;

// TOP
int n, m;

VVI	G;
VI	color;

bool	dfs(int v, int cur = 0)
{
	color[v] = cur;
	for (auto next_v : G[v])
	{
		if (color[next_v] != -1)
		{
			if (color[next_v] == cur)
				return (false);
			continue;
		}
		if (!dfs(next_v, 1 - cur))
			return (false);
	}
	return (true);
}

void	Main()
{
	cin >> n >> m;

	G.resize(n);
	color.assign(n, -1);
	rep(v, m)
	{
		int a, b; cin >> a >> b;

		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	bool	is_bipartite;

	is_bipartite = true;
	if (!dfs(0))
		is_bipartite = false;
	if (is_bipartite)
	{
		int w, b;

		w = 0;
		b = 0;
		rep(v, n)
		{
			if (color[v] == 0)
				w++;
			else
				b++;
		}
		cout << w * b - m << endl;
	}
	else
		cout << n * (n - 1) / 2 - m << endl;
}
// END

int32_t	main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 7424
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

int main(){
    int n;
    cin>>n;
    vector<int> ans;
    ll sum=0,k=0;
    for(int i=1;;i++){
        sum+=i;
        k=i;
        if(sum>n) break;
    }
    for(int i=1;i<=k;i++){
        if(sum-n==i) continue;
        cout<<i<<endl;
    }
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

int a, b, c;

int main(void) {
  // Here your code !
  scanf("%d %d %d", &a, &b, &c);
  
  int whole = a + b + c;
  
  int big = max(max(a, b), c);

  int small = min(min(a, b), c);
  
  int mid = whole - big - small;
  
  printf("%d\n", 10 * big + mid + small);
  
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var o = Console.ReadLine().Replace(" ","").ToInt();
		
		for(int i = 1; i * i <= o; i++)
		{
			if(i * i == o)
			{
				Console.WriteLine("Yes");
				return;
			}
		}
		Console.WriteLine("No");
		
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}


Measured memory_bytes: 13140
#include <iostream>

using namespace std;

int main() {
    int a, b;
    char op;

    while (cin >> a >> op >> b)
        switch (op) {
            case '+':
                cout << a + b << endl;
                break;
            case '-':
                cout << a - b << endl;
                break;
            case '*':
                cout << a * b << endl;
                break;
            case '/':
                cout << a / b << endl;
                break;
            case '?':
                return 0;
                break;
        }
}

Measured memory_bytes: 3080
import sys,resource
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n

d = deque([])
d.append(0)
while len(d)>0:
    i = d.popleft()
    for j in dst[i]:
        v[j] += v[i]
        d.append(j)

for i in range(n):
    printn((' ' if i>0 else '') + str(v[i]))
print("")


Measured memory_bytes: 46624
X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

eat_p = p[:X]
eat_q = q[:Y]
eat = sorted(eat_p + eat_q)

for i in range(min(len(eat), len(r))):
    if eat[i] < r[i]:
        eat[i] = r[i]
    else:
        break

print(sum(eat))

Measured memory_bytes: 23200
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
using ll = long long;
#define max(a,b) ((a)>(b) ? (a):(b))
#define min(a,b) ((a)<=(b) ? (a):(b))
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

int main(){
  long double H;
  cin >> H;
  long double lg = log2(H);
  ll val;
  if(floor(lg) == lg) val = ceil(lg) + 1;
  else val = ceil(lg);
  ll ans = pow(2,val)-1;
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,dp[1<<17],a[1<<17],i;
int main(){
	cin>>n;
	for(i=0;i<n;i++)cin>>a[i];
	reverse(a,a+n);
	fill(dp,dp+n,1<<30);
	for(i=0;i<n;i++)*upper_bound(dp,dp+n,a[i])=a[i];
	cout<<lower_bound(dp,dp+n,1<<30)-dp<<endl;
 }


Measured memory_bytes: 4400
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		double[] x = new double[n];
		double[] y = new double[n];
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			array[i] = i;
		}
		double sum = 0;
		int time = 0;
		do {
			time++;
			double tmp = 0;
			for (int i = 0; i < n - 1; i++) {
				Math.pow(x[array[i]] - x[array[i + 1]], 2);
				double a = Math.pow(x[array[i]] - x[array[i + 1]], 2);
				double b = Math.pow(y[array[i]] - y[array[i + 1]], 2);
				tmp += Math.sqrt(a + b);
			}
			sum += tmp;
		} while (nextPermutation(array));
		System.out.println(sum / time);
		sc.close();
	}

	//順列全列挙
	//nが10を超えてくると間に合わなくなる
	static boolean nextPermutation(int[] array) {
		// Find longest non-increasing suffix
		int i = array.length - 1;
		while (i > 0 && array[i - 1] >= array[i])
			i--;
		// Now i is the head index of the suffix

		// Are we at the last permutation already?
		if (i <= 0)
			return false;

		// Let array[i - 1] be the pivot
		// Find rightmost element that exceeds the pivot
		int j = array.length - 1;
		while (array[j] <= array[i - 1])
			j--;
		// Now the value array[j] will become the new pivot
		// Assertion: j >= i

		// Swap the pivot with j
		int temp = array[i - 1];
		array[i - 1] = array[j];
		array[j] = temp;

		// Reverse the suffix
		j = array.length - 1;
		while (i < j) {
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
			i++;
			j--;
		}

		// Successfully computed the next permutation
		return true;
	}
}

Measured memory_bytes: 37024
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8, i8[:]), cache=True)
def main(H, W, K, XYV):
    G = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        G[x - 1, y - 1] = v
    dp = np.zeros((W + 1, 4), np.int64)
    for h in range(H):
        newdp = np.zeros((W + 1, 4), np.int64)
        for n in range(4):
            newdp[:, 0] = np.maximum(newdp[:, 0], dp[:, n])
        dp = newdp
        for w in range(W):
            for n in range(2, -1, -1):
                # ひろう
                dp[w, n + 1] = max(dp[w, n + 1], dp[w, n] + G[h, w])
            for n in range(4):
                dp[w + 1, n] = max(dp[w + 1, n], dp[w, n])
    return dp.max()

H, W, K = map(int, readline().split())
XYV = np.array(read().split(), np.int64)

print(main(H, W, K, XYV))

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

const int N = 2e5 + 10,M = 1e4 + 10;
char s[N];
int q[M];
ll ans;
int main()
{
    int p,n;
    cin >> n >> p;
    cin >> s+1;

    if(p == 2 || p == 5)
    {
        for(int i = n;i >= 1;i--)
        {
            if((s[i] - '0') % p == 0)ans += i;
        }
    }
    else
    {
        q[0] = 1;int po = 1,res = 0;
        for(int i = n;i >= 1;i--)
        {
            res = (res + (s[i] - '0') * po) % p;
            po = po * 10 % p;
            ans += q[res];//处理到i位时,连续余数和为now的个数是cnt[now],当前余数和now与之前余数和now,作差为０,那么之间的余数和为0的数能找到cnt[now]个，这就是能被p整除的数量。
            q[res]++;
        }
    }    
    cout << ans;

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int N, x;
vector<long long> A;

int main(){
    cin >> N >> x;
    A = vector<long long>(N);
    for(int i=0; i<N; i++){
        cin >> A.at(i);
    }
    
    sort(A.begin(), A.end());
    int ans = 0;
    for(int i = 0; i< N; i++){
        // printf("A %lld\n", A.at(i));
        x -= A.at(i);
        if(x == 0){
            // printf("1\n");
            ans++;
            break;
        }else if(x < 0){
            // printf("2\n");
            break;
        }else{
            if(i != N-1){
                // printf("3\n");
                ans++;
            }
        }
    }

    cout << ans << endl;


}

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

string str = "";

void solve(int n, int l, string s, char cmax){
    if(l == n){
        cout << s << endl;
        return;
    }
    l++;
    cmax++;
    for(char c = 'a';c <= cmax;c++){
        if(c <= cmax){
            cmax--;
            solve(n, l, s += c, max(c, cmax));
            s.pop_back();
            cmax++;
        }
    }
}

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

    string S = "a";
    solve(N, 1, S, 'a');

}

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

int main()
{
	int N;
	int flag = 0;
	int ans = 0;

	cin >> N;

	vector<int> vec(N);
	for (int i= 0; i < N; i++) {
		cin >> vec.at(i);
	}

	while (true) {
		for (int i = 0; i < N; i++) {
			if (vec.at(i) % 2 == 0) {
				vec.at(i) = vec.at(i) / 2;
			}
			else {
				flag = 1;
			}
		}
		if (flag == 1) {
			break;
		}
		else {
			ans += 1;
		}
	}


	cout << ans;
}

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

int main(){
  string N;
  cin >> N;
  int k;
  k = N.size();
  vector<int> vec(k);
  int64_t ans = 0;
  for(int i = 0;i < k;i++){
    if(N.at(i) == '0'){vec.at(i) = 0;}
    else if(N.at(i) == '1'){vec.at(i) = 1;}
    else if(N.at(i) == '2'){vec.at(i) = 2;}
    else if(N.at(i) == '3'){vec.at(i) = 3;}
    else if(N.at(i) == '4'){vec.at(i) = 4;}
    else if(N.at(i) == '5'){vec.at(i) = 5;}
    else if(N.at(i) == '6'){vec.at(i) = 6;}
    else if(N.at(i) == '7'){vec.at(i) = 7;}
    else if(N.at(i) == '8'){vec.at(i) = 8;}
    else {vec.at(i) = 9;}
  }
  for(int i = 0;i < k;i++){
    ans = ans + vec.at(i);
  }
  if(ans % 9 == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 4308
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def main():
    K, N = wi()
    A = wi()
    for i in range(len(A)):
        if i == 0:
            ans = min(K-abs(A[i]+K-A[-1]), K - abs(A[i]-A[i+1]))
        elif i == N - 1:
            ans = min(ans, min(K-abs(K-A[i]+A[0]), K - abs(A[i]-A[i-1])))
        else:
            ans = min(ans, min(K-abs(A[i]-A[i+1]), K - abs(A[i]-A[i-1])))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 71884