akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#define unordered_map __fast_unordered_map
template<class Key, class Value, class Hash = std::hash<Key>>
using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif


int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);

  const int K = 38;
  const int N = K * (K - 1) + 1;
  const int L = K - 1;

  vector<VI> answer(N, VI(K));
  vector<VI> square(L, VI(L));
  for (int i = 0; i < L; ++i)
    for (int j = 0; j < L; ++j)
      square[i][j] = i * L + j + 1;

  for (int i = 0; i < K; ++i)
    answer[0][i] = L * L + i + 1;
  for (int i = 0; i < N - 1; ++i)
    answer[i + 1][0] = L * L + (i / L) + 1;

  for (int layer = 0; layer < L; ++layer) {
    const int start = L * layer + 1;
    for (int r = 0; r < L; ++r)
      for (int c = 0; c < L; ++c)
        answer[start + r][c + 1] = square[(r + c * layer) % L][c];
  }

  const int last_start = N - L;
  for (int r = 0; r < L; ++r)
    for (int c = 0; c < L; ++c)
      answer[last_start + r][c + 1] = square[c][r];

  cout << N << " " << K << "\n";
  for (auto &V : answer) {
    for (int x : V)
      cout << x << " ";
    cout << "\n";
  }
}



Measured memory_bytes: 1024
str = STDIN.gets.gsub(/\R/, "")

s = str.split(/ /)[0].to_i
c = str.split(/ /)[1].to_i

ans = 0

if s*2 < c
  ans += s
  c = c - s*2
  s = 0
else
  ans += c/2
  s = s-c/2
  c = c%2
end

if c > 1
  ans += c/4
end

puts ans


Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

vector<vector<int>>tile(5);

int dis(int dh) {
	int re = 0;
	for (int i = 0; i < dh; i++) {
		if (tile[0][i] == tile[1][i] && tile[1][i] == tile[2][i]) {
			if (tile[0][i] == tile[3][i]) {
				if (tile[0][i] == tile[4][i]) {
					for (int j = 0; j < 5; j++) {
						re += tile[j][i];
						tile[j][i] = 0;
					}
					continue;
				}
				for (int j = 0; j < 4; j++) {
					re += tile[j][i];
					tile[j][i] = 0;
				}
				continue;
			}
			for (int j = 0; j < 3; j++) {
				re += tile[j][i];
				tile[j][i] = 0;
			}
			continue;
		}
		if (tile[2][i] == tile[1][i] && tile[1][i] == tile[3][i]) {
			if (tile[2][i] == tile[4][i]) {
				for (int j = 1; j < 5; j++) {
					re += tile[j][i];
					tile[j][i] = 0;
				}
				continue;
			}
			for (int j = 1; j < 4; j++) {
				re += tile[j][i];
				tile[j][i] = 0;
			}
			continue;
		}
		if (tile[2][i] == tile[3][i] && tile[4][i] == tile[2][i]) {
			for (int j = 2; j < 5; j++) {
				re += tile[j][i];
				tile[j][i] = 0;
			}
			continue;
		}
	}
	return re;
}

void fall(int fh) {
	for (auto &ftile : tile) {
		auto itr = ftile.begin();
		while (itr != ftile.end()) {
			if ((*itr) == 0) {
				itr = ftile.erase(itr);
			}
			else {
				itr++;
			}
		}
		ftile.resize(fh,0);
	}
}

int main() {
	int h;
	while (scanf("%d",&h), h) {
		for (auto &vtile : tile) {
			vtile.resize(h, 0);
		}
		for (int i = 0; i < h; i++) {
			scanf("%d %d %d %d %d", &tile[0][h - i - 1], &tile[1][h - i - 1], &tile[2][h - i - 1], &tile[3][h - i - 1], &tile[4][h - i - 1]);
		}
		int ans = 0;
		while (1) {
			int a;
			a = dis(h);
			if (a)ans += a;
			else break;
			fall(h);
		}
		printf("%d\n", ans);
	}
}

Measured memory_bytes: 3256
#include <stdio.h>
int main()
{
	int h, w, n, hang=0, lie=0, i, counth=0, countl=0;/*hang和lie都是操作次数，而counth和countl是黑色方格的总数，优先比较次数*/
	scanf("%d%d%d", &h, &w, &n);
	for (i = 0;counth < n;i++)
	{
		counth += h;
		hang++;
	}
	for (i = 0;countl < n;i++)
	{
		countl += w;
		lie++;
	}
	if (hang < lie)
	{
		printf("%d", hang);
	}
	else if (lie <= hang)
	{
		printf("%d", lie);
	}
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  vector<vector<int>> e(n);
  int u,v;
  vector<int> deg(n,0);
  rep(i,n-1){
    cin >> u >> v;
    e[u-1].push_back(v-1);
    e[v-1].push_back(u-1);
    deg[u-1]++,deg[v-1]++;
  }
  queue<int> q;
  rep(i,n){
    if(deg[i]==1) q.push(i);
  }
  vector<int> c(n);
  rep(i,n) cin >> c[i];
  sort(all(c));
  LL ans=0;
  rep(i,n-1) ans+=c[i];
  cout << ans << endl;
  vector<int> va(n,-1);
  rep(i,n){
    int now = q.front();
    q.pop();
    va[now]=c[i];
    for(auto nx:e[now]){
      if(deg[nx]>1){
        deg[nx]--;
        if(deg[nx]==1) q.push(nx);
      }
    }
  }
  rep(i,n){
    cout << va[i] << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
    long long int a,b;
    scanf("%lld %lld",&a,&b);
    if(a<0&&b>0||a==0||b==0)
        printf("Zero\n");
    else if(a>0)
        printf("Positive\n");
    else if(b<0)
    {
        if((b-a)%2==0)
            printf("Negative\n");
        else
            printf("Positive\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)

{
	int n, m, x[100][100], y[100], a, b, z[100], k;
	
	scanf("%d %d", &n, &m);
	for (a = 0; a < n; a++)
	{
		z[a] = 0;
	}
	for (a = 0; a < n; a++)
	{
		for (b = 0; b < m; b++)
		{
			scanf("%d", &x[a][b]);
		}
	}
	for (a = 0; a < m; a++)
	{
		
			scanf("%d", &y[a]);
		
	}
	for (a = 0; a < n; a++)
	{
			for (k = 0; k < m; k++)
			{
				z[a] =z[a]+( x[a][k] * y[k]);
			}
		
	}

	for (a = 0; a < n; a++)
	{
				printf("%d", z[a]);
		
		printf("\n");
	}
	return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[100000+1] = {};

    REP(i, n){
        int s;
        cin >> s;
        if(s>0) a[s-1] ++;
        a[s] ++;
        if(s<100000) a[s+1] ++;
    }
    int ans=0;
    REP(i, 100001) ans = max(ans, a[i]);
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? ((x) : -(x)))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
int N, M, K, Q, T;
int ANS[MAXN];
int maxi;
vector<pair<int, int>> graph[MAXN];

void dfs(int u, int p, int color) {
	int c = 1;
	for (int i = 0; i < graph[u].size(); ++i) {
		int v = graph[u][i].first;
		int idx = graph[u][i].second;
		if (v == p) continue;
		while (c == color) ++c;
		maxi = MAX(maxi, c);
		ANS[idx] = c;
		dfs(v, u, c);
		++c;
	}
}


int main()
{
	int i, j, u, v;
	scanf("%d", &N);
	for(i = 1; i<= N - 1; ++i){
		scanf("%d%d", &u, &v);
		graph[u].push_back({v, i});
		graph[v].push_back({ u, i });
	}
	dfs(1, 0, 0);
	printf("%d\n", maxi);
	for (i = 1; i <= N - 1; ++i) printf("%d\n", ANS[i]);
}

Measured memory_bytes: 9344
// 2020 0517 1910
// 要知道 prufer 序.
// 要会计数.
#include <bits/stdc++.h>
#define N 333
using namespace std;
const int mod = 1e9 + 7;

inline int fsp(int x, int p = mod - 2) {
    int res = 1;
    while (p) {
        if (p & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod, p >>= 1;
    }
    return res;
}

int n, d[N], f[N][N][2], fac[N], ifac[N];

inline int cir(int x) {
    return 1ll * fac[x - 1] * ((mod + 1) / 2) % mod;
}

int main() {
#ifdef isLOCAL
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    n = 300;
    for (int i = fac[0] = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = fsp(fac[n]);
    for (int i = n; i >= 1; --i)
        ifac[i - 1] = 1ll * ifac[i] * i % mod;

    cin >> n;
    int flag = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", d + i);
        if (d[i] != 2) flag = 0;
    }
    if (flag) return cout << cir(n) << endl, 0;

    f[0][0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k <= 1; ++k) {
                int &t = f[i][j][k];
                t = (t + 1ll * f[i - 1][j][k] * ifac[d[i] - 1]) % mod;
                if (j && d[i] >= 2)
                    t = (t + 1ll * f[i - 1][j - 1][k] * ifac[d[i] - 2]) % mod;
            }
            if (j && d[i] >= 3)
                f[i][j][1] = (f[i][j][1] + 1ll * f[i - 1][j - 1][0] * ifac[d[i] - 3]) % mod;
        }

    long long ans = 0;
    for (int i = 3; i < n; ++i)
        ans = (ans + 1ll * f[n][i][1] * fac[n - i - 1] % mod * cir(i)) % mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    if (n%2){
        cout << 0 << endl;
        return 0;
    }
    ll cnt = 0;
    ll tmp = n;
    cnt += tmp/10;
    tmp /= 10;
    while(tmp>0) {
        cnt += tmp/5;
        tmp /= 5;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define oit ostream_iterator
#define mod 998244353ll
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
	while (x = getchar_unlocked(), x < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
uniform_real_distribution<double> double_dist(0, 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
int main() {
	doin();
	int n;
	vi a;
	cin >> n;
	ll sum = 0, m = INT_MAX, d = 0;
	getv(a, n);
	for(auto i : a) {
		sum += abs(i);
		if(i < 0)
			d++;
		m = min(abs(i), m);
	}
	if(d&1) sum -= 2*m;
	cout << sum;
	return 0;
}



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

class Dice{
public:
	int l1,l2,l3,l4,l5,l6;
	
	void East(){
		int t = l1;
		l1 = l4;
		l4 = l6;
		l6 = l3;
		l3 = t;
	}
	void West(){
		int t = l1;
		l1 = l3;
		l3 = l6;
		l6 = l4;
		l4 = t;
	}
	void South(){
		int t=l1;
		l1 = l5;
		l5 = l6;
		l6 = l2;
		l2 = t;
	}
	void North(){
		int t=l1;
		l1 = l2;
		l2 = l6;
		l6 = l5;
		l5 = t;
	}
};

int main() {
	
	Dice dice;
	int l1,l2,l3,l4,l5,l6;
	int q;
	int fr,up;
	int i;
	
	cin>>l1>>l2>>l3>>l4>>l5>>l6;
	dice.l1 = l1;
	dice.l2 = l2;
	dice.l3 = l3;
	dice.l4 = l4;
	dice.l5 = l5;
	dice.l6 = l6;
	
	for(cin>>q,i=0;i<q;++i){
		cin>>up>>fr;
		
		if(dice.l1 == fr)dice.South();
		else if(dice.l6 == fr)dice.North();
		else if(dice.l5 == fr){dice.North();dice.North();}
		else if(dice.l3 == fr){dice.West();dice.South();}
		else if(dice.l4 == fr){dice.East();dice.South();}
		
		if(dice.l3 == up)dice.West();
		else if(dice.l4 == up)dice.East();
		else if(dice.l6 == up){dice.East();dice.East();}
		
		cout<<dice.l3<<endl;
	}
}

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


void solve()
{
	int k;
	cin >> k;
	set<int> s1;
	int x = 0, cnt = 0;

	int ans;
	while (1)
	{
		cnt++;
		x = (x * 10 + 7) % k;
		if (x == 0)
		{
			ans = cnt;
			break;
		}
		if (s1.count(x))
		{
			ans = -1;
			break;
		}
		s1.insert(x);
	}
	cout << ans << "\n";
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 50524
def judge(n):
    if n == 2:
        return True
    elif n < 2 or n%2 == 0:
        return False
    else:
        i = 3
        while i<=n**0.5:
            if n%i==0:
                return False
            i = i + 2
    return True        

n = int(input())
num = [int(input().strip()) for _ in range(n)]

sum = 0
for i in range(n):
    if judge(num[i]):
        sum = sum + 1
print(sum)


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

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N,i,j,tmp=0;
    cin >> N;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++) {
            if((i*4+j*7) == N)
                tmp=1;
        }
    }
    if(tmp == 0) cout << "No";
    else cout<< "Yes";
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<vector<ll> >mat;
ll mod=1000000007;
mat e;
void makee(int n)
{
	e.clear();
	e.resize(n);
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			e[i].push_back(i == j);
		}
	}
}
mat tim(mat a, mat b)
{
	mat ret;
	ret.resize(a.size());
	for (int i = 0; i<a.size(); i++)ret[i].resize(b[0].size());
	for (int i = 0; i<a.size(); i++)
	{
		for (int j = 0; j<b[0].size(); j++)
		{
			for (int k = 0; k<a[0].size(); k++)
			{
				ret[i][j] += a[i][k] * b[k][j];
				if (k == ((k >> 3) << 3))ret[i][j] %= mod;
			}
			ret[i][j] %= mod;
		}
	}
	return ret;
}
mat po(mat a, ll b)
{
	if (b == 0)return e;
	mat z = po(a, b / 2);
	z = tim(z, z);
	if (b % 2 == 1)z = tim(z, a);
	return z;
}
int map[1000][1000];
int main()
{
	int mx, my;
	ll kai;
	scanf("%d%d%lld", &mx, &my, &kai);
	kai--;
	for (int i = 0; i < mx; i++)
	{
		for (int j = 0; j < my; j++)
		{
			char z;
			scanf(" %c", &z);
			if (z == '#')map[i][j] = 1;
			else map[i][j] = 0;
		}
	}
	int cx = 0, cy = 0, rx = 0, ry = 0;
	int c = 0;
	for (int i = 0; i < mx; i++)
	{
		for (int j = 0; j < my; j++)
		{
			if (i != 0)rx += map[i - 1][j] & map[i][j];
			else cx += map[mx - 1][j] & map[0][j];
			if (j != 0)ry += map[i][j - 1] & map[i][j];
			else cy += map[i][my - 1] & map[i][0];
			c += map[i][j];
		}
	}
	if (cx > 0 && cy > 0)
	{
		printf("1\n");
		return 0;
	}
	makee(2);
	mat m = e;
	if (cx == 0)
	{
		m[0][0] = c;
		m[0][1] = mod - ry;
		m[1][0] = 0;
		m[1][1] = cy;
	}
	else
	{
		m[0][0] = c;
		m[0][1] = mod - rx;
		m[1][0] = 0;
		m[1][1] = cx;
	}
	mat ret = po(m, kai);
	if (cx > 0 || cy > 0)printf("%lld\n", (ret[0][0] + ret[0][1]) % mod);
	else printf("%lld\n", ret[0][0] % mod);
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
 
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
using namespace std;
 int main() {
   int S, W;
   cin >> S >> W;
   if ( S > W ) {
     cout << "safe" <<endl;
   }
   else {
  cout << "unsafe" << endl;
   }
 }


Measured memory_bytes: 3636
from operator import itemgetter

n, m = map(int, input().split())

# 区間の終端でソート
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)


Measured memory_bytes: 18980
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int S, N, a;
int main() {
	cin >> S >> N;
	int ret = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		int res = (a >= S / 2 ? a - (S - a) - 1 : 0);
		ret = max(ret, res);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <istream>
#include <algorithm>
#include <vector>
#include <string>

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

	std::size_t n;
	std::cin >> n;

    std::vector<std::size_t> v;
    v.reserve(n);

    for (std::size_t i = 0; i < n; ++i) {
        std::size_t l;
        std::cin >> l;
        v.emplace_back(l);
    }
    std::size_t acc = 0;
    std::size_t max = 0;
    for (const auto e: v) {
        acc += e;
        max = std::max(e, max);
    }
    std::cout << (((acc - max) > max) ? "Yes" : "No") << std::endl;
  
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  double W,H;
  double x,y;
  cin>>W>>H>>x>>y;
  if(x+x==W && y+y==H){
  	cout<<fixed<<setprecision(1);
    cout<<W*H/2<<" "<<1<<endl;
  }
  else{
    cout<<fixed<<setprecision(1);
    cout<<W*H/2<<" "<<0<<endl;
  }    
    
}

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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(int i = (int)m; i < (int)n; i++)
#define rep(i,n) REP(i,0,n)
#define rep2(i,n) REP(i,1,n+1)
#define rep3(i,n) REP(i,0,n+1)
#define REPM(i,m,n) for(int i = (int)m; i >= (int)n; i--)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define repll(i,n) REPLL(i,0,n)
#define repll2(i,n) REPLL(i,1,n+1)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define Size(s) (int) s.size()

//------------------------------------------------------

int main() {
    int n, x;
    cin >> n >> x;
    if (2 <= x && x <= 2 * n - 2) {

        Yes(true);
        if (n == 2) {
            printf("1\n2\n3\n");
        } else {

            queue<int> que;

            if (x == 2) {

                rep2(i, 2 * n - 1) if (i < x - 1 || i > x + 2) que.push(i);

                rep(i, n - 2) {
                    printf("%d\n", que.front());
                    que.pop();
                }

                printf("%d\n%d\n%d\n%d\n", x + 1, x, x - 1, x + 2);

                while (!que.empty()) {
                    printf("%d\n", que.front());
                    que.pop();
                }

            } else {
                rep2(i, 2 * n - 1) if (i < x - 2 || i > x + 1) que.push(i);

                rep(i, n - 2) {
                    printf("%d\n", que.front());
                    que.pop();
                }

                printf("%d\n%d\n%d\n%d\n", x - 1, x, x + 1, x - 2);

                while (!que.empty()) {
                    printf("%d\n", que.front());
                    que.pop();
                }
            }

        }
    } else {
        Yes(false);
    }

    return 0;
}

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

using namespace std;

string s;

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

	cin >> s;
	bool ok = true;
	for (int i=0;i<=2;i++)
		if (s[i] == s[i+1])
		{
			ok = false;
			break;
		}
	if (ok)
		cout << "Good\n";
	else
		cout << "Bad\n";	
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))

hq = []
for a in A:
    heapq.heappush(hq, -a)

while M > 0:
    high = -1 * heapq.heappop(hq)
    high //= 2
    M -= 1
    heapq.heappush(hq, -high)

ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

print(-ans)

Measured memory_bytes: 14200
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using ull = unsigned long long;
using ll = long long;
using namespace std;

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

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> b = a;
    for(int i = 0; i <n ; ++i) {
        b[i] -= i+1;
    }

    sort(b.begin(), b.end());
    int median = int(ceil(n/2));
    int bconst = b[median];

    size_t saddness = 0;
    for(int i = 0; i < n; ++i) {
        saddness += abs(a[i]-(bconst+i+1));
    }


    cout << saddness << endl;

    return 0;
}

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

int main(){
  int N;
  cin>>N;
  vector <string> vs;
  vector <int> vc;
  string s;
  bool fl;
  for (int i=0;i<N;i++){
    cin>>s;
    fl=0;
    for (int j=0;j<vs.size();j++){
      if (s==vs.at(j)){
        vc.at(j)++;
        fl=1;
        break;
      }

    }
    if (fl==0){
      vs.push_back(s);
      vc.push_back(1);
    }
  }
  int M;
  cin>>M;
  for (int i=0;i<M;i++){
    cin>>s;
    fl=0;
    for (int j=0;j<vs.size();j++){
      if (s==vs.at(j)){
        vc.at(j)--;
        fl=1;
        break;
      }

    }
    if (fl==0){
      vs.push_back(s);
      vc.push_back(-1);
    }
  }
  int ans=0;
  for (int i=0;i<vs.size();i++){
    if (vc.at(i)>ans){
      ans=vc.at(i);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <string>
#include <stack>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int n,q,times=0;
pair<string,int> process1;
queue<pair <string,int> > Q;
void solve()
{
    while(!Q.empty())
    {
        process1=Q.front();Q.pop();
        if(process1.second<=q)
        {
            times+=process1.second;
            cout<<process1.first<<" "<<times<<endl;
        }
        else
        {
            times+=q;
            process1.second-=q;
            Q.push(process1);
        }
    }
}
int main()
{
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        cin>>process1.first>>process1.second;
        Q.push(process1);
    }
    solve();
    return 0;
}


Measured memory_bytes: 6212
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>                                                                                                                                              
#include <numeric>
#include <functional>
#include <cstdlib>
#include <regex>
#include <list>
	int main() {
		int N, M;
		std::cin >> N >> M;
		std::cout << (1900 * M + 100 * (N - M))* std::pow(2, M) << std::endl;
		return 0;
	}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;


int main() {
    string S;
    cin >> S;
    cout << S.at(0) << S.at(1) << S.at(2) << endl;
    
}

Measured memory_bytes: 3580
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    long a[] = new long[n];
    int flg = 0;
    long sum = 0;
    long max = 0;
    long min = Long.MAX_VALUE;
    int cnt = 0;

    for (int i=0; i<n; i++) {
      a[i] = Integer.parseInt(sc.next());
      if (a[i] < 0) {
        a[i] = -1 * a[i];
        cnt++;
      }
      if (a[i] < min) {
        min = a[i];
      }
      sum += a[i];
    }
    
    if (cnt%2 == 1) {
	  sum -= 2*min;
    }
    
    System.out.println(sum);
  }
}


Measured memory_bytes: 48748
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

string s;

int main() {
  init_ios();
  cin >> s;
  if (s[2] == s[3] && s[4] == s[5])
    cout<<"Yes\n";
  else
    cout<<"No\n";
}

Measured memory_bytes: 256
def main():
    from collections import Counter
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    a_count = Counter(A)
    b_count = Counter(B)
    for k,v in (a_count + b_count).items():
        if N < v:
            print('No')
            return
    print('Yes')
    C = [0]*(N+1)
    idx = 0
    for a in A:
        while idx < a:
            idx += 1
            C[idx] = C[idx-1]
        C[idx] += 1
    while idx < N:
        idx += 1
        C[idx] = C[idx-1]

    D = [0]*(N+1)
    idx = 0
    for b in B:
        while idx < b:
            idx += 1
            D[idx] = D[idx-1]
        D[idx] += 1
    while idx < N:
        idx += 1
        D[idx] = D[idx-1]
    
    x = 0
    for i in range(1,N+1):
        x = max(x, C[i] - D[i-1])
        # print(x)
    print(*(B[N-x:]+B[:N-x]))
    # print(C)
    # print(D)

main()


Measured memory_bytes: 198708
import java.util.Scanner;

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

		int n = sc.nextInt();
		int[] clr = new int[8];
		int free = 0;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if (a >= 3200) {
				free++;
			} else {
				clr[a / 400] = 1;
			}
		}

		int min = 0;
		for (int i : clr) {
			min += i;
		}

		int max = min;

		if (min < 1) {
			min = 1;
		}

		for (int i = 0; i < free; i++) {
			max++;
		}

		System.out.println(min + " " + max);
		sc.close();
	}
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int xy[2];
  
  while (1) {
      
      cin >>xy[0] >>xy[1];
      
      if (xy[0]==0 && xy[1]==0) {
          break;
      }
      
      cout << min(xy[0],xy[1]) << ' ' << max(xy[0],xy[1]) << endl;
  }
  
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
 
 
void solve(){
  string main;
  cin>>main;
  if(main[3]==main[2] && main[5]==main[4]) cout<<"Yes"<<'\n';
  else cout<<"No"<<"\n";
  return;
}



int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int t=1;
  //cin>>t;
  while(t--) solve();
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int n,z,w,a[2005];
int main(){
	cin>>n>>z>>w;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1) cout<<abs(a[1]-w)<<endl;
	else cout<<max(abs(a[n]-w),abs(a[n-1]-a[n]));
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
fn main(){
 let mut s=String::new();
 stdin().read_line(&mut s).unwrap();
 let w = s.trim().to_lowercase();
 let mut s=String::new();
 stdin().read_to_string(&mut s).unwrap();
 println!("{}",s.to_lowercase().split_whitespace().fold(0,|a,s|{if s==w{a+1}else{a}}))
}


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

using namespace std;

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

int main() {
	int a, b;
	cin >> a >> b;

	vector<int> c(16);
	if (a > 0) {
		c[0] = 1;
		a--;
	}
	else {
		c[0] = 2;
		b--;
	}

	FOR(i, 1, 16) {
		if (a > 0 && c[i - 1] != 1 && c[(i + 1) % 16] != 1) {
			a--;
			c[i] = 1;
		}
		else if (b > 0 && c[i - 1] != 2 && c[(i + 1) % 16] != 2) {
			b--;
			c[i] = 2;
		}
	}
	if (a > 0 || b > 0) {
		cout << ":(" << endl;
	}
	else {
		cout << "Yay!" << endl;
	}



	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# n = int(input())
n = input()
s = list(input())
# a,b,c = map(int, input().split())
# d = list(map(int, input().split()))
tmp = ""
ans = ""
for word in s:
  if word != tmp:
    ans += word
  tmp = word
print(len(ans))

Measured memory_bytes: 4084
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include <string>

using namespace std;
 
int main() {
    int n;cin>>n;
    if(n == 1){cout<<"Hello World";return 0;}
    int a,b;cin>>a>>b;
    cout<<a+b;
    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#include <boost/foreach.hpp>
using namespace std;
#define pi 2*asin(1.0)
#define MAX 10000000
#define MOD 1000000007
#define _GLIBCXX_DEBUG
 
vector<long> fac(MAX);
vector<long> finv(MAX);
vector<long> inv(MAX);
vector<long> Primelist;
//template functions
/////////////////////////
void Prinit(){
long PR=10000001;
vector<long> P(PR,0);
for(long i=2;i*i<PR;i++){
    if(P.at(i)==0){
        long j=i;
      j+=i;
        while(j<PR){
            P.at(j)=1;
             j+=i;         
        }
    }
}

for(long i=2;i*i<PR;i++){//Primelist.size()=446
    if(P.at(i)==0){
        Primelist.push_back(i);
    }
}
}

void Cominit(){
  fac.at(0)=fac.at(1)=1;
  finv.at(0)=finv.at(1)=1;
  inv.at(1)=1;
  for(long i=2;i<MAX;i++){
      fac.at(i)=(fac.at(i-1)*i)%MOD;
      inv.at(i)=MOD-inv.at(MOD%i)*(MOD/i)%MOD;
      finv.at(i)=finv.at(i-1)*inv.at(i)%MOD;
  }
}

long facComb(long N,long M){// nCm%
if(N<M) return 0;
if(N<0||M<0) return 0;
return fac.at(N)*(finv.at(M)*finv.at(N-M)%MOD)%MOD;
}

long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}

long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}

long GCM(long A,long B){
            long W,r;
    if(A<B){

        W=B;
        B=A;
        A=W;
    }
    while(A%B!=0){
        r=A%B;
        A=B;
        B=r;
    }
    return B;
}
long LCM(long A,long B){
    return (A*B)/GCM(A,B);
}

long upDiv(long a,long b){
  return (a+b-1)/b;
}

long strtolong(string str){
istringstream ss;
ss=istringstream(str);
long num;
ss>>num;
return num;
}

long chartolong(char ch){
long num;
num=ch-'0';
return num;
}

long Max2(long a,long b){
if(a>b){
    return a;
}else{
    return b;
}
}

long Min2(long a,long b){
if(a>b){
    return b;
}else{
    return a;
}
}


string longtostr(long N){
    string str;
    str=to_string(N);
    return str;
}









/////////////////////////


//Answer


int main() {
Prinit();
long N,K,ans=0;
cin>>N>>K;
vector<long> h(N);
for(long i=0;i<N;i++){
cin>>h.at(i);
if(h.at(i)>=K){
    ans++;
}
}
cout<<ans<<endl;



}


Measured memory_bytes: 315636
H, W = map(int, input().split())
S = ["........................................................"]
for i in range(H):
    S.append(input())
for i in range(H+1):
    S[i] = '.' + S[i] + '.'
S.append("........................................................")
ans = [[0] * W for i in range(H)]

for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == '#':
            ans[i-1][j-1] = '#'
        else:
            count = []
            for a in range(i-1, i+2):
                for b in range(j-1, j+2):
                    count.append(S[a][b])
            ans[i-1][j-1] = count.count('#')

for i in range(H):
    yoko = ''
    for j in range(W):
        yoko += str(ans[i][j])
    print(yoko)


Measured memory_bytes: 3064
import java.util.*;

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

		while(sc.hasNextInt()){
			int value = sc.nextInt();
			if(value != 0){
				n.add(value);
			}
			else{
				break;
			}
		}

		for(int i = 0; i < n.size(); i++){
			System.out.println("Case " + (i + 1) + ": " + n.get(i));
		}
	}
}

Measured memory_bytes: 44324
n, l = map(int, input().split())
li = []
for i in range(l,l+n):
    li.append(i)

start = li[0]
end = li[n-1]

if start >= 0:
    li[0] = 0
elif end <= 0:
    li[n-1] = 0
    
print(sum(li))


Measured memory_bytes: 3060
N = int(input())
A = list(map(int, input().split()))
res = 0
ans = 0
right = 0
for left in range(N):
    while right < N and (res ^ A[right]) == res + A[right]:
        res += A[right]
        right += 1
    ans += (right - left)
    if left == right:
        right += 1
    res -= A[left]
print(ans)

Measured memory_bytes: 24840
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

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

    float L;
    cin>>L;
    long double ans;
    long double c = L/3.0;
    L-=c;
    long double b = L/2.0;
    if(c*b*b > c*c*c) ans = c*b*b;
    else ans=c*c*c;
    cout<<fixed<<setprecision(12)<<ans<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
#include <cctype>
using namespace std;
using ll = long long;
const int mod = 1000000007;

ll gcd(ll a, ll b){return b ? gcd(b,a%b) : a;};//最大公約数
ll lcm(ll a, ll b){return a*b/gcd(a,b);};//最小公倍数
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//typedef pair<ll,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
//ll a[100000];
//ll dom[100001];

int main(){
  int n;
  cin>>n;
  int a[n];
  int flag=0;//1があるかどうか
  for(int i=0;i<n;++i){
    cin>>a[i];
    if(a[i]==1) flag=1;
  }
  int ans=0;
  if(flag==0) {
    cout<<-1;
    return 0;
  }else{
    for(int i=0;i<n;++i){
      if(a[i]==ans+1) ans++;
    }
  }
  cout<<n-ans<<endl;
   return 0;
}

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

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

    int r, g, b, n;
    cin >> r >> g >> b >> n;

    int ans = 0;
    for(int i = 0; i <= n / r; i++){
        for(int j = 0; j <= n / g; j++){
            int t = i * r + j * g;
            if((n - t) % b == 0 and (n - t) >= 0){
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
program main
  implicit none
  integer i
  character(10) S
  read(*, *) S
  !read(*, *) (L(i), i = 1,N)
  if (trim(S) == 'Sunny') then
    write(*, *) 'Cloudy'
  else if (trim(S) == 'Cloudy') then
    write(*, *) 'Rainy'
  else if (trim(S) == 'Rainy') then
    write(*, *) 'Sunny'
  end if
end program main


Measured memory_bytes: 640
#include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> tup;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vp;
int ans=10000;
int main(int argc,char const* argv[])
{
  int p,q,r;
  cin >> p >> q >> r;
  ans=min(p+q,ans);
  ans=min(p+r,ans);
  ans=min(q+r,ans);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
#define PI 3.141592653589793238
int main()
{
  cout.setf(ios::fixed);
	cout.setf(ios::showpoint);
	cout.precision(15);
  double a,b,h,m,p=30,q,r=6,o,s,t,y;
  cin>>a>>b>>h>>m;
  p*=h;
  q=m*0.5;
  p+=q;
  r*=m;
  o=p-r;
  t=a*a+b*b;
  y=cos((o*PI)/180.000000000);
  y*=2*a*b;
  t-=y;
  t=sqrt(t);
  cout<<t;
}

Measured memory_bytes: 4188
from collections import Counter

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d
      
n, x, y = [int(i) for i in input().split()]

dij = Dijkstra(n)

for i in range(n-1):
  dij.add(i, i+1, 1)
dij.add(x-1, y-1, 1)

c = Counter([])
for i in range(n):
  c.update(dij.shortest_path(i))

for i in range(1, n):
  print(c[i]//2)



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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N;
    cin>>N;
    vi A(N);
    REP(i, 0, N){
        cin >> A[i];
    }
    sort(A.rbegin(), A.rend());
    long ans = 0;
    REP(i, 1, N) ans += A[(int)(i/2)];
    cout << ans << endl;
}

Measured memory_bytes: 4052
let rec gcd a b =
  match a mod b with
  | 0 -> b
  | r -> gcd b r

let lcm a b = a / (gcd a b) * b


let f n =
  let rec g n' ans =
    if n' = 0 then ans
    else g (pred n') (lcm ans (read_int ()))
  in
  g n 1

let () = f (read_int ()) |> Printf.printf "%d\n"

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
#define INF 1000000001
typedef struct vertice
{
  int cost;
  int status;
  int numOfAdj;
  int *adjList;
  int *costList;
} ver;
ver *v;
int n;//the number of vertices
void init();
void setArray(int);
void dijkstra(void);
int main(void)
{
  int i,j;//counter
  int key;
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++)
    {
      scanf("%d",&key);
      scanf("%d",&v[key].numOfAdj);
      setArray(key);
      for(j=0;j<v[key].numOfAdj;j++) scanf("%d%d",&v[key].adjList[j],&v[key].costList[j]);
    }
  dijkstra();
  free(v);
  return 0;
}
void init(void)
{
  int i;//counter
  v=(ver*)malloc(sizeof(ver)*n);
  for(i=0;i<n;i++)
    {
      v[i].numOfAdj=0;
      v[i].status=0;
      v[i].cost=INF;
    }
}
void setArray(int key)
{
  v[key].adjList=(int*)malloc(sizeof(int)*v[key].numOfAdj);
  v[key].costList=(int*)malloc(sizeof(int)*v[key].numOfAdj);
}
void dijkstra(void)
{
  int i;//count
  int current=0;
  int viewing;
  int next;
  int minCost;
  v[0].cost=0;
  for(;;)
    {
      v[current].status=1;
      minCost=INF;
      for(i=0;i<v[current].numOfAdj;i++)
	{
	  viewing=v[current].adjList[i];
	  if(v[viewing].status==0)
	    {
	      if(v[current].cost+v[current].costList[i]<v[viewing].cost)
		{
     		  v[viewing].cost=v[current].cost+v[current].costList[i];
		  //printf("v[%d].cost=%d\n",viewing,v[viewing].cost);
		}
	    }
	}
      for(viewing=0;viewing<n;viewing++)
	{
	  if(v[viewing].status==0&&v[viewing].cost<minCost)
	    {
	      minCost=v[viewing].cost;
	      next=viewing;
	    }
	}
      if(minCost==INF) break;
      //printf("next->%d\n",next);
      current=next;
    }
  for(i=0;i<n;i++) printf("%d %d\n",i,v[i].cost);
}




Measured memory_bytes: 5620
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<climits>
using namespace std;

enum{BLANK='.',WALL='*'};
struct Data{int height,pos;};

int main()
{
  int W,H,ans;
  vector<string>field;
  vector< vector<int> >dp;
  while(cin>>H>>W,H|W){
    field.resize(H);
    for(int i=0;i<H;i++)cin>>field[i];
    dp.resize(H);
    for(int i=0;i<H;i++)dp[i].resize(W+1);
    for(int j=0;j<W;j++)dp[0][j] = (field[0][j]==WALL)?0:1;
    for(int i=0;i<H;i++)dp[i][W] = INT_MIN;
    for(int i=1;i<H;i++)for(int j=0;j<W;j++)dp[i][j] = (field[i][j]==WALL)?0:dp[i-1][j]+1;

    //for(int i=0;i<H;i++,puts(""))for(int j=0;j<W+1;j++)cout<<dp[i][j]<<", ";

    ans=0;
    for(int i=0;i<H;i++){
      stack<Data>s;
      for(int j=0;j<W+1;j++){
	Data d1={dp[i][j],j},d2;
	int newPos;
	if(s.empty()){
	  s.push(d1);
	}else if(s.top().height < d1.height){
	  s.push(d1);
	}else if(s.top().height == d1.height){
	}else if(s.top().height > d1.height){
	  d2=d1;
	  while(!s.empty() && s.top().height >= d1.height){
	    d2=s.top();
	    s.pop();
	    ans = max(ans, (d1.pos-d2.pos)*d2.height);
	    newPos=d2.pos;
	  }
	  d1.pos=newPos;
	  s.push(d1);
	}
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = sorted(iil(),reverse=True)[1::2]
print(sum(A[:n]))


Measured memory_bytes: 37188
#include <stdio.h>

int main(){
	int w;

	while(1){
		scanf("%d",&w);
		if(w==-1)break;
		if(w<=10)printf("3130\n");
		else if(w<=20)printf("%d\n",3130-125*(w-10));
		else if(w<=30)printf("%d\n",1880-140*(w-20));
		else printf("%d\n",480-160*(w-30));
	}
	return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <iterator>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 2019

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

typedef long long ll;
typedef pair<ll, ll> p;

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(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = int(s.size());
  reverse(ALL(s));
  vector<mint> v(n);
  mint ten = 10;
  rep(i, n) v[i] = mint(s[i] - '0') * ten.pow(i);
  vector<mint> dp(n+1);
  ll res = 0;
  map<int, int> mp;
  for (int i = 1; i < n+1; ++i) {
    dp[i] = dp[i-1] + v[i-1];
  }
  for (int i = 0; i < n+1; ++i) {
    res += mp[dp[i].x];
    mp[dp[i].x]++;
  }
  cout << res << endl;

}


Measured memory_bytes: 6804
#include <stdio.h>
int main(){
  int even = 0;
  int ans = 1;
  while(1) {
    int c = getchar ();
    if (c == EOF) {
      break;
    } else if (even == 1 && c == 'R') {
      ans = 0;
    } else if (even == 0 && c == 'L') {
      ans = 0;
    }
    even = (even + 1) % 2;
  }
  if (ans == 1) {
    puts("Yes");
  }else{
    puts("No");
  }
  return 0;
}


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

int main(){
	int a,b;
	cin>>a>>b;
	if(b%2!=0){
		cout<<"No"<<endl;
		return 0;
	}else{
		if(a*4<b||a*2>b){
			cout<<"No"<<endl;
			return 0;
		}
		cout<<"Yes"<<endl;
	}
}


Measured memory_bytes: 3628
from math import ceil
from itertools import permutations


def ret(perm):
    now = 0
    for i in range(4):
        now += perm[i]
        now = ceil(now / 10) * 10
    now += perm[-1]
    return now


X = [int(input()) for _ in range(5)]
perms = permutations(X)
ans = 1e100
for perm in perms:
    ans = min(ans, ret(perm))
print(ans)



Measured memory_bytes: 3188