akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

#define ll long long
#define pb push_back

int main(){

	int K, N;
	vector<int> H;

	cin >> N >> K;
	for(int i = 0; i < N; i ++){
		int h;
		cin >> h;
		H.pb(h);
	}
	sort(H.begin(), H.end());
	int max = 1000000010;
	for(int i = 0; i < N - K + 1; i ++){
		//cout << "debug" << H[i + K - 1] - H[i] << endl;
		max = min(max, H[i + K - 1] - H[i]);
	}
	cout << max << endl;

	return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  string S;
  cin >> S;
  int o = 0;
  int x = 0;
  REP(i, 0, S.length()) {
    if (S[i] == 'o')
      o++;
    else
      x++;
  }
  DUMP(o,x);
  while (o + x < 15) {
    o++;
  }
  DUMP(o,x);
  if (o >= 8) {
    cout << "YES" << endl;
  } else
    cout << "NO" << endl;

  return 0;
}


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

template<class T>
inline set<T> divisorsList(T n) {
    set<T> div;
    for (T i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            div.insert(i);
            if (i * i != n)
                div.insert(n / i);
        }
    }
    return div;
}

template<class T>
inline T cntDigit(T num) {
	T cnt = 0;
	while (num) {
		num /= 10;
		cnt++;
	}
	return cnt;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);

	ll N;
	cin >> N;

	ll res = 0;
	set<ll> d = divisorsList(N);
	ll n = d.size();
	auto itr = d.begin();
	REP(i, n / 2) itr++;
	res = cntDigit(*itr);

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


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;

char str[maxn];
vector<int> v[33];

int main(){
	int ans = 0;
	scanf("%s", str);
	int n = strlen(str);

	int cnt = 0;	// stevilo lihih (drugacnih od 'x')
	for(int i = 0; i < n; i++)
		v[str[i] - 'a'].pb(i);

	for(int i = 0; i < 33; i++){
		if(i != ('x' - 'a') && v[i].size() % 2)
			cnt++;
	}

	if(cnt > 1){
		printf("-1\n");
	}

	if(cnt <= 1){
		int l = 0;
		int d = n - 1;

		while(l < d){
			if(l >= 0 && d < n && str[l] == str[d]){
				l++;
				d--;
				continue;
			}

			if(l >= 0 && str[l] == 'x'){
				ans++;
				l++;
				continue;
			}

			if(d < n && str[d] == 'x'){
				ans++;
				d--;
				continue;
			}
			ans = -1;
			break;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1148
#include <iostream>

using namespace std;

int main()
{
    int ans=0;
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++)
    {
     if(s[i]=='7')
            ans++;
    }
    cout << (ans>0 ? "Yes":"No");
    return 0;
}


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

using namespace std;
int read(){
	int r=0,f=1;
	char c = getchar();
	while(!isdigit(c)){
		if(c == '-') f = -1;
		c = getchar();
 	}
 	while(isdigit(c)){
 		r = (r<<1)+(r<<3)+c - '0';
 		c = getchar();
	 }
	 return r*f;
}
int main(){
	int a[6];
	for(int i=1;i<=5;i++){
		a[i] = read();
	}
	for(int i=1;i<=5;i++){
		if(a[i] == 0)
		cout<<i<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 3604
#include <cstdio>
#include <map>
#include <algorithm>

typedef long long ll;

const int MaxN = 20040313 + 19260817;
const ll infl = 1ll << 60;

int A, B, C, D; ll K;
std::map<ll, ll> dp;

inline int Abs(int x) {
	return x > 0 ? x : -x;
}

ll dfs(ll n) {
	if (n == 0) return 0;
	if (n == 1) return D;
	auto [it, flag] = dp.insert({n, n > K ? infl : n * D});
	ll &ans = it->second;
	if (!flag) return ans;
	for (ll i = std::max(n - 4, 0ll); i <= n + 4; ++i) {
		ll t = (ll)D * Abs(n - i);
		if (i % 2 == 0) ans = std::min(ans, A + t + dfs(i / 2));
		if (i % 3 == 0) ans = std::min(ans, B + t + dfs(i / 3));
		if (i % 5 == 0) ans = std::min(ans, C + t + dfs(i / 5));
	}
	return ans;
}

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		ll n;
		scanf("%lld%d%d%d%d", &n, &A, &B, &C, &D);
		K = infl / D;
		dp.clear();
		printf("%lld\n", dfs(n));
	}
	return 0;
}

Measured memory_bytes: 6236
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 1<<17;

vector<pii> T[MX];
int state[MX], val[MX];
int N, ans = 0;

void dfs(int x, int p = -1){
	state[x] = 0;
	for(pii e : T[x]){
		int c = e.second, d = e.first;
		if( c == p ) continue;
		dfs(c, x);

		for(int i = 1; i < 16; i++) if( state[c]&1<<i ) d ^= i;
		if( d && state[c]&1<<d ) ans++;
		state[c] ^= 1<<d;
		for(int i = 1; i < 16; i++){
			if( state[c]&1<<i && state[x]&1<<i ){
				state[x] ^= 1<<i;
				state[c] ^= 1<<i;
				ans++;
			}
		}
		state[x] |= state[c];
	}
}

int chk(int x){
	int c = 0, v = 0;
	for(int i = 1; i < 16; i++){
		if( x&1<<i-1 ) v ^= i, c++;
	}
	if( c == 1 ) return 1;
	if( v ) return -1;
	return c-1;
}


int main()
{
	scanf("%d", &N);
	for(int i = 1; i < N; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		T[a].emplace_back(c, b);
		T[b].emplace_back(c, a);
	}
	for(int i = 1; i < 1<<15; i++){
		val[i] = 1e9;
		for(int j = i; j; j = (j-1)&i){
			int v = chk(j);
			if( v != -1 ) val[i] = min(val[i], val[i^j] + v);
		}
	}
	for(int i = 0; i < 1; i++){
		ans = 0;
		dfs(i);
		printf("%d\n", val[state[i]/2] + ans);
	}
}


Measured memory_bytes: 14464
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define sz(x) (int)(x.size())
#define mod 1000000007
#define endl "\n"
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;



int32_t main(){
    ios::sync_with_stdio(false);
    int n, k;
    cin>>n>>k;
    int ans=0;	
    int small=0;
    int large=(n*(n+1))/2;
    for(int i=k;i<=(n+1);i++){
    	small=(i-1)*i/2;
    	large=(n-i+1)*i+(i*(i-1))/2;
    	ans=(ans+(large-small+1))%mod;
    }
    cout<<ans<<"\n";

    return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

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

		if (13 <= A) {
			System.out.println(B);
		} else if (6 <= A && A <= 12) {
			System.out.println(B / 2);
		} else {
			System.out.println(0);
		}
	}
}


Measured memory_bytes: 21716
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

class UnionFind {
private:
	unsigned size_; 
	std::vector<unsigned> par, rank;
public:
	UnionFind() : size_(0), par(std::vector<unsigned>()), rank(std::vector<unsigned>()) {};
	UnionFind(unsigned size__) : size_(size__) {
		par.resize(size_); rank.resize(size_);
		for (unsigned i = 0; i < size_; i++) par[i] = i, rank[i] = 0;
	}
	unsigned size() { return size_; }
	//unsigned root(unsigned x) { return par[x] == x ? x : par[x] = root(par[x]); }
	unsigned root(unsigned x)
	{
		while(par[x] != x)
		{
			par[x] = par[par[x]];
			x = par[x];
		}
		return x;
	}
	bool same(unsigned x, unsigned y) { return root(x) == root(y); }
	void unite(unsigned x, unsigned y) {
		x = root(x), y = root(y);
		if (x == y) return;
		if (rank[x] < rank[y]) par[x] = y;
		else if (rank[x] == rank[y]) par[y] = x, rank[x]++;
		else par[y] = x;
	}
	bool operator==(const UnionFind &u) { return par == u.par; }
	bool operator!=(const UnionFind &u) { return par != u.par; }
};


__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}


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

	ll N;
	
	cin >> N;

	ll a[N], b[N];

	ll c[N];

	ll d = 0;

	rep(i, N)
	{
		cin >> a[i] >> b[i];
		c[i] = a[i] + b[i];
		d += b[i]; 
	}

	sort(c, c+N);
	ll sum = 0;
	for(int i = N-1; i >= 0; i-=2)
	{
		sum += c[i];
	}

	cout << (sum - d) << endl;

	
	return 0;
}


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

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

const ll mod =  1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

int main()
{
    int n;    cin >> n;
    string s; cin >> s;
    ll ans = 0;
    ll r = 0, g = 0, b = 0;
    rep(i,n){
        if(s[i] == 'R') r++;
        if(s[i] == 'G') g++;
        if(s[i] == 'B') b++;
    }
    ll sub = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            int k = j + (j-i);
            
            if(k < n && s[i] != s[j] && s[j] != s[k] && s[i] != s[k]) sub++;
        }
    }
    ans = r*b*g - sub;
    cout << ans << endl;
}


Measured memory_bytes: 3636
n = int(input())
h = list(map(int, input().split()))
import sys


if n == 1:
  print('Yes')
  sys.exit()


for i in range(1, n):
  if not(h[i] >= h[i-1]):
    if not(h[i] == h[i-1]-1):
      print('No')
      sys.exit()
    else:
      h[i] = h[i-1]
print('Yes')


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

int main() {
  long long n;
  cin >> n;
  
  long long ans = n;
  for (int i = 1; i <= sqrt(n); ++i) {
    if (n%i == 0)
      ans = min(ans, i + n/i - 2);
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

string a, b;

int read_num(int& p, string& s)
{
	int res = 0;
	while (p < s.size() && isdigit(s[p]))
	{
		res *= 10;
		res += s[p] - '0';
		p++;
	}
	return res;
}

string solve(int la, int ra, int lb, int rb)
{
	if (ra == la || rb == lb) return "()";
	int lla, lra, rla, rra;
	int cnt = 0, pa = la, pb = lb;
	for(pa = la; pa < ra; pa++)
	{
		if (a[pa] == '(') cnt++;
		if (a[pa] == ')') cnt--;
		if (cnt == 0) break;
	}
	pa++;
	lla = la;
	lra = pa;
	assert(a[pa] == '[');
	pa++;
	int vala = read_num(pa, a);
	assert(a[pa] == ']');
	pa++;
	rla = pa;
	rra = ra;

	int llb, lrb, rlb, rrb;
	cnt = 0;
	for (pb = lb; pb < rb; pb++)
	{
		if (b[pb] == '(') cnt++;
		if (b[pb] == ')') cnt--;
		if (cnt == 0) break;
	}
	pb++;
	llb = lb;
	lrb = pb;
	assert(b[pb] == '[');
	pb++;
	int valb = read_num(pb, b);
	assert(b[pb] == ']');
	pb++;
	rlb = pb;
	rrb = rb;
	string res = "(" + solve(lla + 1, lra - 1, llb + 1, lrb - 1) + "[" + to_string(vala + valb) + "]" + solve(rla + 1, rra - 1, rlb + 1, rrb - 1) + ")";
	return res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> a >> b;
	string res = solve(0, a.size(), 0, b.size());
	cout << res.substr(1, res.size() - 2) << endl;
	return 0;
}

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

int main(){
  int N,L;
  cin >> N >> L;
  
  string s;
  
  vector<string> v;
  for(int i=0; i<N; i++){
    cin >> s;
    v.push_back(s);
  }
  
  sort(v.begin(), v.end());
  for(int i=0; i<N; i++){
    cout << v.at(i);
  }
}
  


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

void hanafuda_shuffle(int p,int c,vi &A){
    vi a,b;
    rep(i,p-1){
        a.eb(A[i]);
    }
    rep(i,c){
        b.eb(A[i+p-1]);
    }
    rep(i,c){
        A[i]=b[i];
    }
    rep(i,p-1){
        A[i+c]=a[i];
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    while(true){
        int n,r; cin >> n >> r;
        if(n==0 && r==0) break;
        vi A(n);
        rep(i,n) A[i]=n-i;
        rep(j,r){
            int s,t; cin >> s >> t;
            hanafuda_shuffle(s,t,A);
        }
        cout << A[0] << endl;
    }
}


Measured memory_bytes: 3148
#include <cstdio>
#include <ctype.h>

using namespace std;

int N;
bool A[210000];

int main()
{
	char tt;
	long long ans = 0, cnt = 0;
	
	while (!isalpha(tt = getchar()));
	A[N = 1] = tt == 'B';
	if (A[N])
		++cnt;
	while (isalpha(tt = getchar())) {
		A[++N] = tt == 'B';
		if (A[N])
			++cnt;
	}

	for (int i = 1; i <= N; ++i)
		if (A[i])
			ans += N - cnt + 1 - i, --cnt;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 384
N, K = map(int, input().split())
ans = 0
if K == 0:
    ans = N**2
else:
    for b in range(1, N+1):#bを動かす、aの個数はわかる
        p, r = N // b, N % b
        ans += p*max(0, b-K) + max(0, r-K+1)

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
using ll=long long;
ll n,a,b;
int main()
{
	cin>>n>>a>>b;
	if (n<=a+b-2 || n>a*b)
	{
		cout<<-1<<endl;
		return 0;
	}
	vector <ll> res;
	for (ll i=b-1;i>=0;--i) res.push_back(i);
	if (a!=1)
	{
		ll rem=n-b,p=rem/(a-1),r=rem%(a-1);
		ll b=r,c=a-1-r;
		for (int i=0;i<b;++i)
		{
			int t=sz(res);
			for (int j=0;j<p+1;++j)
			{
				res.push_back(t+p-j);
			}
		}
		for (int i=0;i<c;++i)
		{
			int t=sz(res);
			for (int j=0;j<p;++j)
			{
				res.push_back(t+p-1-j);
			}
		}
	}
	for (int i=0;i<sz(res);++i)
	{
		cout<<res[i]+1;
		if (i!=sz(res)-1) cout<<" ";
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 6384
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        int n = in.nextInt();
        int d = in.nextInt();
        d = 2*d+1;
        out.println((int)Math.ceil(n/(d+.0)));
        
    }
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 21332
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

int n;
ld p[3000];

ld cache[3000][3000];

ld dp(ll idx, ll heads){
    if(idx>n){
        if(2*heads>=n) return 1.0;
        else return 0;
    }
    ld &ans=cache[idx][heads];
    if(ans!=-1) return ans;
    ans=p[idx]*dp(idx+1,heads+1)+(1-p[idx])*dp(idx+1,heads);
    return ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    rep(i,1,n+1) cin >> p[i];
    mst(cache,-1);
    ld res=dp(1,0);
    cout << fixed << setprecision(20) << res;
    return 0;
}

Measured memory_bytes: 141312
x, y, a, b, c = map(int,input().split())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
R = list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

#print(P)
#print(Q)
#print(R)

p = 0
q = 0
r = 0
ans = 0
for i in range(x+y):
    if p < x:
        red = P[p]
    else:
        red = 0
    if q < y:
        green = Q[q]
    else:
        green = 0
    if r < c:
        white = R[r]
    else:
        white = 0
    
    choice = max(red, green, white)
    #print(choice)
    ans += choice
    
    if choice == red:
        p += 1
    elif choice == green:
        q += 1
    else:
        r += 1
print(ans)
    
    

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

int main(){
    int K, S;
    cin >> K >> S;
    int counter = 0;

    for (int i = 0; i <= K; ++i){
        for (int j = 0; j <= K; ++j){
            int tmp = S - i - j;
            if (tmp >= 0 && tmp <= K) ++counter;
        }
    }
    cout << counter << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a,b,c;
    cin >> a >> b >> c; 
    cout << a[0] << b[1] << c[2] << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2 or P == 5:
        n = 0
        ans = 0
        for c in reversed(S):
            if int(c) % P == 0:
                n += 1
            ans += n
        return ans

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c) % P
        c = a
        if a == 0:
            ans += 1
        ans += p[a]
        p[a] += 1
        t = (t * 10) % P

    return ans


def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6600
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>
 
using namespace std;
using ll = long long;
// constexpr int MOD = 1e9+7;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
ll gcd(ll a, ll b){ return (b == 0) ? a : gcd(b, a % b); }
ll lcm(ll a, ll b){ return a/gcd(a, b)*b; };
 
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Unique(a) a.erase(unique(Range(a)), a.end());
#define Reverse(c) reverse(Range(c))
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, n, xs, sxs) vector<T> sxs(n+1); For(i, n) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

int main(void){
    Cin(string, s);
    ll ans = 0;
    For(bit, 1 << (s.size()-1)){
        ll a = 0;
        for(int i = 0; i < (int)s.size(); i ++){
            a = 10*a + (int)(s[i] - '0');
            if(bit & (1 << i) || i == (int)s.size()-1){
                ans += a;
                a = 0;
            }
        }
    }
    Cout(ans);
}


Measured memory_bytes: 256
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
let suuji = readInts()
let n = suuji[0]
let l = suuji[1]
var sum = 0
var min = l
for i in 2...n {
  var b = l + i - 1
  sum+=b
  if (abs(b)<abs(min)) {
    sum-=b
    sum+=min
    min=b
  }
}
print(sum)

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

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<mint> sum(n+1);
    rep(i,n){
        sum[i+1] += a[i];
        sum[i+1] += sum[i];
    }
    mint ans = 0;
    rep(i,n){
        mint tmp = (sum[n]-sum[i+1]);
        tmp *= a[i];
        ans += tmp;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5616
def b_picking_up(N, Positions):
    if N == 1:
        return 1  # 最初のボールに移動するのは必ずコスト1

    from collections import defaultdict
    difference_count = defaultdict(int)  # xの差分とyの差分の組について、現れた回数

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            # diff_x と diff_y がともに0となることは、入力の制約よりありえない
            diff_x = Positions[j][0] - Positions[i][0]
            diff_y = Positions[j][1] - Positions[i][1]
            difference_count[(diff_x, diff_y)] += 1
    return N - max(difference_count.values())  # 第2項はコスト0で移動できる座標の数

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(b_picking_up(N, Positions))

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


int main()
{
  int n;
  cin >> n;
  unordered_map<string, int> m;
  ll ans = 0;
  rep(i, n)
  {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    ans += m[s];
    m[s]++;
  }
  cout << ans << endl;
  return 0;
}


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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();

		int N = Integer.parseInt(str);

		String[] str2 = br.readLine().split(" ");;

		int[] w = new int[N];
		for(int i=0;i<N;i++) {
			w[i] = Integer.parseInt(str2[i]);
		}


		int abs = 0;
		for(int i=0;i<N;i++) {
			int suml = 0;
			int sumr = 0;

			for(int j=0;j<N;j++) {
				if(j<=i) {
					suml += w[j];
				}else {
					sumr += w[j];
				}
			}

			if(i==0) {
				abs = Math.abs(suml - sumr);
			}else if(abs>Math.abs(suml - sumr)) {
				abs = Math.abs(suml - sumr);
			}else {
				break;
			}

		}


		System.out.println(abs);

	}
}


Measured memory_bytes: 21204
n =  int(input())
nums = list(map(int,input().split(" ")))

def countingSort(A,N):
    C = [0]*(max(A)+2)

    for i in range(N):
        C[A[i]] += 1

    for i in range(1,len(C)):
        C[i] = C[i] + C[i-1]


    B = [0]*N
    for i in range(n-1,-1,-1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

    return B

ans = countingSort(nums,n)
print(' '.join(map(str,ans)))



Measured memory_bytes: 240324
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <tuple>
//#include <functional>
#include <cstring>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i <= n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i <= n; i++)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<double> v_double;
typedef std::vector<std::vector<double> > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<std::vector<bool> > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

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

using namespace std;

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

    ll ans = (n / (a+b)) * a + min(a, (n % (a+b)));
    cout << ans << endl;
    return 0;
}
/** atcoder **/


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <set>
#include <map>
#include <numeric>

int main() {
  intmax_t a, b, k;
  scanf("%jd %jd %jd", &a, &b, &k);

  if (a >= k) {
    a -= k;
  } else {
    k -= a;
    a = 0;
    b -= k;
    if (b < 0) b = 0;
  }
  printf("%jd %jd\n", a, b);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(20)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;

void solve() {
	int n;
	cin >> n;
	int sum = 0;
	vi v(n);
	mii mp;
	rep(i, 0, n - 1) {
		cin >> v[i];
		mp[v[i]]++;
		sum += v[i];
	}
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		sum -= mp[a] * a;
		mp[b] += mp[a];
		sum += mp[a] * b;
		mp[a] = 0;
		cout << sum << "\n";
	}
}

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


#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// test
	solve();

	return 0;
}

Measured memory_bytes: 9952
import collections

n,k = map(int, raw_input().split(' '))
xis = map(int, raw_input().split(' '))
ais = [xi for xi in xis if xi >= 0]
bis = [-xi for xi in xis if xi < 0][::-1]
m = ais[k -1] if k-1 < len(ais) else +float('inf')
m = min(m, bis[k -1] if k-1 < len(bis) else +float('inf'))

for i in range(len(ais)):
	if i + 1 == k: break
	if 0 <= k - (i+1) -1 < len(bis):

		m = min(m, 2*ais[i] + bis[k - (i+1) -1])
		m = min(m, ais[i] + 2*bis[k - (i+1) -1])
print m

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

ll N, L;
string S[1000];

int main(void) {
  cin >> N >> L;
  REP(i, 0, N) cin >> S[i];

  sort(S, S + N);

  ll p[1000];
  REP(i, 0, N) p[i] = -1;
  REP(i, 0, N) if(p[i] == -1) {
    // string s = reverse(S[i].begin(), S[i].end());
    string s = "";
    REP(j, 0, S[i].size()) s += S[i][S[i].size() - j - 1];
    // cout << S[i] << " " << s << endl;
    REP(j, i + 1, N) if(p[j] == -1) {
      if(s == S[j]) {
        p[i] = j;
        p[j] = i;
        break;
      }
    }
  }

  string ans = "";
  vector<string> mid;
  REP(i, 0, N) if(p[i] >= 0) {
    ans += S[i];
    p[p[i]] = -2;
  } else if(p[i] == -1) {
    bool f = true;
    REP(j, 0, S[i].size()) f = f && S[i][j] == S[i][S[i].size() - j - 1];
    if(f) mid.push_back(S[i]);
  }
  sort(mid.begin(), mid.end());

  // cout << (ans + reverse(ans.begin(), ans.end())) << endl;
  cout << ans;
  if(mid.size() > 0) cout << mid[0];
  REP(i, 0, ans.size()) cout << ans[ans.size() - i - 1];
  cout << endl;
}

Measured memory_bytes: 3292
import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        String str = sc.next();
        if(n%2!=0) {
            p("No");
            return;
        }
        String s1 = str.substring(0,n/2);
        String s2 = str.substring(n/2,n);
        if(s1.equals(s2)) {
            p("Yes");
        }else {
            p("No");
        }
    }
    public static <T> void p(T element) {
	System.out.println(element);
    }
    public static <T> void pp(T element) {
        System.out.print(element);
        }
    public static int min(int a, int b, int c) {
	int min = Math.min(a,b);
	min = Math.min(min,c);
	return min;
    }
    public static int max(int a, int b,int c) {
	int max= Math.max(a,b);
	max = Math.max(max,c);
        return max;
    }
}
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
 
    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }
 
    private boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
 
    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }
 
    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
 
    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
 
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }
 
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 21332
inf = float('inf')
# ベルマンフォード法 計算量(VE)
# [引数]: 隣接リスト, 始点, 終点
class Bellmanford:
    def __init__(self, to : list, start : int, goal : int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N
    
    # self.distを更新
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
    
    # グラフの負閉路検出
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle
    
    # スタートからゴールまでのパスの負閉路検出
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

N, M, P = map(int,input().split())
to = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C -= P
    to[A].append((B, -C))

BF = Bellmanford(to, 0, N-1)
BF.update()

if BF.detection_stog():
    ans = -1
else:
    ans = max(-BF.dist[N-1], 0)

print(ans)

Measured memory_bytes: 57816
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e18;
const ll MOD=1e9+7;

int main(){
    int n;cin>>n;
    vector<ll> A(n);
    for(int i=0;i<n;++i){
        cin>>A[i];
    }
    ll ans=0;
    ll sum=0;
    int right=0;
    for(int left=0;left<n;++left){
        while(right<n&&(sum^A[right])==sum+A[right]){
            sum+=A[right];
            ++right;
        }
        ans+=(right-left);
        if(left==right) ++right;
        else sum-=A[left];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4848
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
ll f(ll b,ll n) {
	if (n<b) return n;
	else return f(b,n/b)+(n%b);
}
ll solve(ll n, ll s) {
	{
		ll lim=sqrt(n)+5;
		for (ll b=2;b<=lim;b++) {
			if (f(b,n)==s) return b;
		}
	}
	{
		ll lim=sqrt(n)+5;
		ll ans=INF;
		for (ll x=1;x<=lim;x++) {
			ll y=s-x;
			if (y<0) continue;
			ll lhs=n-y;
			if (lhs%x==0) {
				ll b=lhs/x;
				//if (x==1) printf("ddx:%lld lhs:%lld b:%lld\n",x,lhs,b);
				if (b>=lim&&x<b&&y<b) {
					//printf("x:%lld lhs:%lld b:%lld\n",x,lhs,b);
					chkmin(ans,b);
				}
			}
		}
		if (n==s) chkmin(ans,n+1);
		if (ans>=INF) return -1;
		return ans;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	ll n,s; cin>>n>>s;
	cout<<solve(n,s)<<endl;
}

Measured memory_bytes: 256
/*
  AOJ 1516
  Title:
  @kankichi573
*/
#include <stdio.h>
#include <string.h>
#define NUM 1000

char string[11];

adjoin(char x,char y)
{
  int i;

  x -= 'A';
  y -= 'A';

  if(x-y == 3||y-x == 3)
    return(-1);
  if(x-y == 1&&(x % 3)>0)
    return(-1);
  if(y-x == 1&&(y % 3)>0)
    return(-1);
  return(0);
}
int check(char s[])
{
  int i,len=strlen(s);

  if(len==1)
    return(-1);
  for(i=0;i<len-1;i++)
    if(!adjoin(s[i],s[i+1]))
      return(0);
  return(-1);
}
main()
{
  int i;

  for(i=0;i<NUM;i++)
    {
      scanf("%s",string);
      if(check(string))
	printf("%s\n",string);
    }
  return(0);
}

Measured memory_bytes: 524
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		String[] spl = sc.nextLine().split(" ");
		int[] h = new int[N];
		for(int i = 0;i < N;i++) {
			h[i] = Integer.parseInt(spl[i]);
		}
		sc.close();

		String ans = "Yes";
		for(int i = N-1;i > 0;i--) {
			if(h[i] - h[i-1] < 0) {
				h[i-1] -= 1;
				if(h[i] - h[i-1] < 0) {
					ans = "No";
				}
			}
		}
		System.out.println(ans);
	}
}

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

int main(){
  int m, f, r;
  vector<int> t, k, s;
  while(true){
    cin >> m >> f >> r;
    if(m==-1 && f==-1 && r==-1) break;

    t.push_back(m); k.push_back(f); s.push_back(r);
  }

  for(int i=0; i<(int)t.size(); i++){
    char res;
    if(t[i]==-1 || k[i]==-1) res='F';
    else if(t[i]+k[i]>=80) res='A';
    else if(t[i]+k[i]>=65 && t[i]+k[i]<80) res='B';
    else if(t[i]+k[i]>=50 && t[i]+k[i]<65) res='C';
    else if(t[i]+k[i]>=30 && t[i]+k[i]<50){
      if(s[i]>=50) res='C';
      else res='D';
    }
    else res='F';

    cout << res << endl;
  }

  return 0;
}



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

int main() {
	double a, b, x;
	cin >> a >> b >> x;
	double s = x / a;
	double rad;
	if (s >= a * b / 2) {
		double h = (a * b - s) * 2 / a;
		rad = atan2(h, a);
	} else {
		double w = s * 2 /b;
		rad = atan2(b, w);
	}
	double PI = acos(-1);
	double deg = rad / (2 * PI) * 360;
	printf("%.10f\n", deg);
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    int minus_cnt = 0;
    ll absmin = 1e10;
    int pos = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i] <= 0) minus_cnt++;
        if(abs(a[i]) < absmin)
        {
            absmin = abs(a[i]);
            pos = i;
        }
    }
    ll ans = 0;
    if(minus_cnt % 2 == 0)
    {
        for(int i = 0; i < n; i++)
        {
            ans += abs(a[i]);
        }
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            if(i == pos)
            {
                ans -= abs(a[i]);
            }
            else
            {
                ans += abs(a[i]);
            }
        }
    }
    cout << ans << endl;
}



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

int mem[9][1<<9];
int n , m ;
vector<int>v[9];

int dp(int i,int x){
if( x+1 == 1<<n )return 1;
int &ret = mem[i][x];
if( ret != -1 )return ret;
ret=0;

for(auto j:v[i])
    if( !(x&( 1<<j )) )
        ret+=dp(j,x+(1<<j));
return ret;
}

int main(){
memset(mem,-1,sizeof mem);
cin>>n>>m;
while( m-- ){
    int x , y ;cin>>x>>y;
    x--;y--;
    v[x].push_back(y);
    v[y].push_back(x);
}
cout<<dp(0,1)<<endl;
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
const int MAX = 2e5;
const ll INF = 2e9;

ll a[MAX], dp[MAX], ans[MAX];
vector<vector<int>> g(MAX);

void lis_tree(int u, int p) {
  int prep = lower_bound(dp,dp+MAX,a[u]) - dp;
  ll prev = dp[prep];
  dp[prep] = a[u];
  ans[u] = lower_bound(dp,dp+MAX,INF) - dp;
  for(auto e : g[u]) {
    if(e != p) lis_tree(e,u);
  }
  dp[prep] = prev;
}

int main(){
  int n;
  cin >> n;
  rep(i,n) cin >> a[i];
  rep(i,n-1) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  rep(i,MAX) dp[i] = INF;
  lis_tree(0,-1);
  rep(i,n) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 33168