akhauriyash/Code-Regression huggingface dataset:
n,k = map(int,input().split())
a = list(map(int,input().split()))
res1 = 0
res2 = 0
for i in range(0,n):
    res1 += len([sa for sa in a if sa < a[i] ])
    res2 += len([sa for sa in a[i:] if sa < a[i] ])

print((res2 *  k + res1 * k*(k-1) // 2) % (10** 9 + 7))

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

const ll infll=9223372036854775806;
const int inf=2147483646;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	int a,b,c,d,e,k;
	cin>>a>>b>>c>>d>>e>>k;
	if (e-a>k){
		cout<<":(";
	}
	else {
		cout<<"Yay!";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
vector<ll> a(n),b(n,0);
for(int i=0;i<n;i++)cin>>a[i];
ll tmp=1,ans=0,bfo=0;
bool ok=true;
while(ok){
    ok=false;
    ll cnt=0,tmp=0,t;
   for(int i=0;i<n;i++){
          cnt+=(a[i]+bfo-b[i])/n;
          t=(a[i]+bfo-b[i])/n;
          a[i]=(a[i]+bfo-b[i])%n;
          b[i]=t;
   }
   ans+=cnt;
   bfo=cnt;
   for(int i=0;i<n;i++){
       if((a[i]+bfo-b[i])>=n)ok=true;
   }
}
cout<<ans<<endl;
}

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

int main() {
	int ans, temp;
	while (1) {
		cin >> ans; if (ans == 0) break;
		for (int i = 0; i < 9; i++) {
			cin >> temp; ans = ans - temp;
		}
		cout << ans << endl;
	}
	return 0;
}


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

#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define FOR(i,a,b)  for(int i=(a); i< (b); ++i)
#define RFOR(i,b,a) for(int i=(b);i>=(a);i--)
#define REP(i,a,b)  for(int i=(a); i<=(b); ++i)
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
template<typename T>
void PrArr(const T a[] , int len){
	for(int i = 0;i <= len; i++)cout << a[i] << " ";
	cout << endl;
}
template<typename T>
void PrVec(const vector<T> a){
	for(auto it : a)cout << it << " ";
	cout << endl;
}
const int MAX = 0x7ffffff;
const int MIN = 0xcf;
int test;
void slove()
{
	int n; cin >> n;
	vector<int> a(n + 1);
	for(int i = 1;i <= n ;i ++)cin>> a[i];
	sort(a.begin() + 1,a.begin() + n + 1);
	ll ans = 0;
	int k = n / 2;
	for(int i = k + 2;i <= n - 1;i ++)
	{
		ans += 2*(ll)a[i];
	}	
	if(n > 1)ans += a[n];
	if(n > 2){
		if(n & 1)ans += a[k + 1];
		else ans += 2 * a[k + 1];
	}
	cout << ans << endl;
} 
int main()
{
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed; // 在iomanip中
#endif
	SIS;slove();
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

Measured memory_bytes: 3972
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

ll A, B, N;

signed main(){
    cin >> A >> B >> N;
    if(N < B){
        cout << A*N/B - A*(N/B) << endl;
        return 0;
    }
    ll tmp = (N+1) / B;
    tmp = tmp * B;
    tmp--;
    cout << A*tmp/B - A*(tmp/B) << endl;
}

Measured memory_bytes: 3592
using System;
class Program{
	public static void Main(){
		int N = int.Parse(Console.ReadLine());
		long[] L = new long[N + 1];
		L[0] = 2;
		L[1] = 1;
		if (N >= 2){
			for (int i = 2; i <= N; i++){
				L[i] = L[i - 1] + L[i - 2];
			}
		}
		Console.WriteLine(L[N]);
	}
}

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

using namespace std;
using Int = long long;

signed main(){
    Int n;
    vector<Int> a, b;
    cin >> n;

    for(Int i = 0; i < n + 1; i++){
        Int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    for(Int i = 0; i < n; i++){
        Int tmp;
        cin >> tmp;
        b.push_back(tmp);
    }

    Int l = 0;
    Int r = n - 1;
    Int cnt = 0;
    while(l <= r){
        //left
        if (a[l] + a[l+1] < b[l]){
            cnt += a[l] + a[l + 1];
            b[l] -= a[l] + a[l + 1];
            a[l] = 0;
            a[l + 1] = 0;
        } else{
            cnt += b[l];
            if ( a[l] < b[l] ){
                b[l] -= a[l];
                a[l] = 0;
                a[l + 1] -= b[l];
                b[l] = 0;
            } else {
                a[l] -= b[l];
                b[l] = 0;
            }
        }
        l++;
        if(l > r) break;

        //right
        if (a[r] + a[r+1] < b[r]){
            cnt += a[r] + a[r + 1];
            b[r] -= a[r] + a[r + 1];
            a[r] = 0;
            a[r + 1] = 0;
        } else{
            cnt += b[r];
            if ( a[r + 1] < b[r] ){
                b[r] -= a[r + 1];
                a[r + 1] = 0;
                a[r] -= b[r];
                b[r] = 0;
            } else {
                a[r + 1] -= b[r];
                b[r] = 0;
            }
        }
        r--;
        if(l > r) break;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 2548
// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

void sputs(){}
template <class Head, class... Tail>
void sputs(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(Tail) == 0) { cout << endl; }
  else { cout << " "; }
  sputs(std::move(tail)...);
}

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}
#define N 31
string to_bin(int n, int d){
  // nをd桁の2進数で表示する。
  stringstream ss;
  ss << bitset<N>(n);
  return ss.str().substr(N-d, d);
}
// int d = (32 - __builtin_clz(n));  // 桁数
// int f = N - d; to_bin()で返ってきた文字列で最初に1が立っているindex


signed main() {
  int n;cin>>n;
  int k;cin>>k;
  vi a(n),b(n);
  rep(i,n)cin>>a[i]>>b[i];
  dump(to_bin(k, 10));

  int ans = -INF;
  int res = 0;
  rep(i, n){
    if (((a[i])&~k)==0) res += b[i];
  }
  chmax(ans, res);
  dump(ans);

  rep(d, 0, 31){
    // d桁目を0
    if (k>>d&1){
      int res = 0;
      rep(i, n){
        dump(i, a[i]>>(d+1), k>>(d+1));
        if (((a[i]>>(d+1))&(~(k>>(d+1))))==0 && !(a[i]>>d&1)) res += b[i];
      }
      dump(d, res);
      chmax(ans, res);
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

int main(){
   int N;
   std::cin >> N;
   std::vector<int> a(N);
   for (auto &x : a){
      std::cin >> x;
   }
   std::map<int, int> mp;
   for (auto x : a){
      mp[x-1]++;
      mp[x]++;
      mp[x+1]++;
   }
   int ans = 0;
   for (auto x : mp){
      ans = std::max(ans, x.second);
   }
   std::cout << ans << std::endl;
}



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

int main() {
  int a, b;
  cin >> a >> b;
  if (a < b) {
    cout << "a < b" << endl;
  } else if (a > b) {
    cout << "a > b" << endl;
  } else {
    cout << "a == b" << endl;
  }
  return 0;
}


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


typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
/*--------------------------------------------*/

int ans(string x){
  if(x == "SUN")return 7;
  if(x == "MON")return 6;
  if(x == "TUE")return 5;
  if(x == "WED")return 4;
  if(x == "THU")return 3;
  if(x == "FRI")return 2;
  if(x == "SAT")return 1;
}

int main(){
 //cout.precision(10);
 cin.tie(0);
 ios::sync_with_stdio(false);
  
  string s;
  cin  >> s;
  
  cout << ans(s) << endl;
  

}


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;

int main() {
  int n,k,r,s,p;
  cin >> n >> k >> r >> s >> p;

  string t;
  cin >> t;

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if(i - k >= 0 && t[i] == t[i - k]) {
      t[i] = '?';
      continue;
    }

    if(t[i] == 'r') ans += p;
    if(t[i] == 's') ans += r;
    if(t[i] == 'p') ans += s;
  }

  cout << ans << '\n';
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }

const ll INF=1e18;

class UnionFind{
public:
	vector<ll> par,num;
 
	ll find(ll v){
		return (par[v]==v)? v: (par[v]=find(par[v]));
	}
	explicit UnionFind(ll N):par(N),num(N,1){
		iota(par.begin(),par.end(),0);
	}
	void unite(ll u,ll v){
		u=find(u),v=find(v);
		if(u==v)return ;
		if(num[u]<num[v])swap(u,v);
		num[u] += num[v];
		par[v] = u;
	}
	bool same(ll u,ll v){
		return find(u) == find(v);
	}
	bool ispar(ll v){
		return v=find(v);
	}
	ll size(ll v){
		return num[find(v)];
	}
};

int main(){
    ll n,m;
    cin>>n>>m;
    UnionFind G(n);
    V<ll> a(m),b(m);
    rep(i,m){
        cin>>a[i]>>b[i];
        a[i]--;b[i]--;
        G.unite(a[i],b[i]);
    }
    V<ll> e(3,0);
    rep(i,m){
        if(G.same(0,a[i])||G.same(0,b[i])) e[0]++;
        else if(G.same(1,a[i])||G.same(1,b[i])) e[1]++;
        else e[2]++;
    }
    ll ans=0;
    V<ll> v(3);
    rep(i,2) v[i]=G.size(i);
    v[2]=n-v[0]-v[1];
    ll v_max;
    if(v[0]>v[1]) v_max=0;
    else v_max=1;
    ll v_min=v_max^1;
    ans+=v[v_min]*(v[v_min]-1)/2-e[v_min];
    ll u=v[v_max]+v[2];
    ans+=u*(u-1)/2-e[v_max]-e[2];
    cout<<ans<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
(全探索できるなら全探索しろ)
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'\n'
*/

Measured memory_bytes: 3456
#include <stdio.h>
#include <stdlib.h>

int hantei(int);
  
int main()
{
  int i,n,seisuu,cnt=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&seisuu);
    if(hantei(seisuu)) cnt++;
  }
  printf("%d\n",cnt);
}

int hantei(int seisuu)
{
  int i;
  
  if(seisuu == 2) return 1;
  else if(seisuu%2 == 0) return 0;
  if(seisuu < 2) return 0;
  
  for(i=3;i*i<=seisuu;i++){
    if(seisuu%i == 0) return 0;
  }
  return 1;
}



Measured memory_bytes: 2048
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

int main() {
        double a, b;
        scanf("%lf%lf", &a, &b);
        printf("%.9lf\n", a * b / (a + b));
        return 0;
}



Measured memory_bytes: 256
from operator import itemgetter
N,H = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
a = max(ab,key=itemgetter(0))[0]
b = sorted([i[1] for i in ab if i[1] > a],reverse=True)
count = 0
for i in b:
    count += 1
    H -= i
    if H <= 0:
        break
if H > 0:
    count += H//a + (0 if H%a==0 else 1)
print(count)

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

#define mem(arr, i) fill(arr, arr + sizeof(arr), i)
#define MEM(arr, i) memset(arr, i, sizeof(arr))
#define Push push_back
#define Pair make_pair
#define ALL(x) x.begin(), x.end()
#define X first
#define Y second
#define ACCEL ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef pair<pll,lli> p3l;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
typedef vector<p3l> v3L;
typedef vector<vcL> vvL;
//typedef priority_queue<T> prior_S<T>;
//typedef priority_queue< T, vector<T>, greater<T> > prior_B<T>;
const double PI = 3.141592653589793;
const lli I_MAX = 1LL << 60;
      lli   mod = 1000000007;

/// templates ///

const lli maxN = 2E5;

vcL inv(maxN+5, 1);
vcL fac(maxN+5, 1);

void ADD(lli &x, lli y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

void MUL(lli &x, lli y) {
	x *= y;
	x = (x % mod + mod) % mod;
}

lli mypow(lli b, lli e) {
	lli ans = 1;
	while (e) {
		if (e & 1) MUL(ans, b);
		MUL(b, b);
		e >>= 1;
	}
	return ans;
}

lli modinv(lli n) {
	return mypow(n, mod - 2);
}

void calcInv(lli n) {
	for (int i = 2; i <= n; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
}

void calcFac(lli n) {
	for (int i = 2; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
}

lli cm(lli a, lli b) {
	lli ans = 1;
	if (a < b) return 0;

	MUL(ans, inv[fac[a - b]]);
	MUL(ans, inv[fac[b]]);
	MUL(ans, fac[a]);

	return ans;
}

lli Lucas(lli n, lli m) {
	if (m == 0) return 1;
	return cm(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}

lli doLucas(lli n, lli m) {
	calcInv(mod);
	calcFac(mod);
	return Lucas(n, m);
}

/// coding area ///

const lli maxn = 1E5;

void precal() {

	return;
}

void solve() {
	lli n, d;
	cin >> n >> d;
	cout << n / (2 * d + 1) + (n % (2 * d + 1) != 0) << '\n';
}

int main() {
	precal();
	int t = 1;
	#ifdef LOCAL
		t = INT_MAX;
	#else
		ACCEL;
	#endif
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
//		printf("Case #%d: ", i );
		solve();
	}
	return 0;
}



Measured memory_bytes: 3328
[_x, _n] = list(map(int, input().split(" ")))
if _n == 0:
  print(_x)
else:
  _list = list(map(int, input().split(" ")))
  _answer = 0
  _flag = False

  if _x not in _list or _n == 0:
    _answer = _x
    _flag = True
  else:
    for _i in range(_n):
      if _i % 2 == 0:
        if _x - _i//2 - 1 not in _list and _flag == False:
          _answer = _x - _i//2 - 1
          _flag = True
      else:
        if _x + _i//2 + 1 not in _list and _flag == False:
          _answer = _x + _i//2 + 1
          _flag = True
  print(_answer)

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


int main() {
    ll  n;
    cin>>n;
    long long r=0,l=0;
    cin>>l>>r;
    for (int i = 1; i < n; ++i) {
        ll lla,rr;
        cin>>lla>>rr;
        ll ra = max((ll)(r + rr - 1) / rr, (ll)(l + lla - 1) / lla);
        l=lla*ra;
        r=rr*ra;
    }
    cout<<r+l<<endl;
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  int ac=0,wa=0,tle=0,re=0;
  rep(i,0,n){
    string s;
    cin >> s;
    if(s[0]=='A') ac++;
    else if(s[0]=='W') wa++;
    else if(s[0]=='T') tle++;
    else re++;
  }
  printf("AC x %d\n",ac);
  printf("WA x %d\n",wa);
  printf("TLE x %d\n",tle);
  printf("RE x %d\n",re);
  return 0;
}

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

#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define lb(v, z) lower_bound(all(v), z)
#define ub(v, z) upper_bound(all(v), z)
#define fill(a, z) memset(a, z, sizeof(a))
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rdp(i, a, b) for (int i = (a); i >= (b); i--)
#define rlt(i, a, b) for (int i = (a); i < (b); i++)
#define cns(z) cout << z << ' '
#define cnl(z) cout << z << '\n'
#define printclock cerr << "Time : " << 1000 * (double)clock() / (double)CLOCKS_PER_SEC << "ms\n";
#define M 1000000007
#define M2 998244353
#define MAXN 300005
#define INF 1000000000000
#define endl "\n"
#define iip(t) \
	int t;     \
	cin >> t;
#define iip2(a, b) \
	int a, b;      \
	cin >> a >> b;
#define dip(a) \
	double a;  \
	cin >> a;
#define dip2(a, b) \
	double a, b;   \
	cin >> a >> b;
#define garr(ip)       \
	for (auto &x : ip) \
		cin >> x;
#define parr(ip)          \
	for (auto &x : ip)    \
		cout << x << " "; \
	cout << endl;
#define test   \
	int _t;    \
	cin >> _t; \
	while (_t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vp;

int modExp(int base, int exponent = M - 2, int MOD = M)
{
	if (exponent == 0)
		return 1;
	int curr = modExp(base, exponent >> 1);
	curr = (curr * curr) % MOD;
	if (exponent & 1)
		curr = (curr * base) % MOD;
	return curr;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	iip2(s, w);
	cnl(((s <= w) ? "unsafe" : "safe"));
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        ll N;
        cin >> N;
        if (N == 0)
            break;
        vector<ll> A(N);
        REP(i, N) {
            cin >> A[i];
        }
        ll s = 0;
        ll sum = 0;
        ll ans = -INF;
        REP(i, N) {
            sum += A[i];
            while (sum <= 0 && s < i)
                sum -= A[s++];
            while (A[s] < 0 && s < i)
                sum -= A[s++];
            ans = std::max(ans, sum);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long int k,a,b,max=1;
    long long int c=1;
    cin >> k >> a >> b;
    if(b-a<2){
        c=k+1;
//        cout << k+1 << endl;
    }else if(k+1<=a){
        c=k+1; 
    }else{
        k-=a-1;
        c+=a-1;
//        cout << k << endl;
        c+=k%2;
//        cout << k%2 << endl;
        c+=(k/2)*(b-a);
//        cout << (k/2) << endl;
//        cout << (b-a) << endl;
//        cout << (k/2)*(b-a) << endl;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
typedef long long ll;

int main(){

  ll N, A, B; cin >> N >> A >> B;
  vector <ll> H(N);

  ll start = 0, end = 0;
  for (int i = 0; i < N; i++){
    cin >> H[i];
    end += H[i] / B;
    if (H[i] % B != 0) end++;
  }


  vector < pair<ll, bool> > result;
  result.push_back(make_pair(0, false));
  result.push_back(make_pair(end, true));
  
  int C = 0;
  while (C <= 1){
    ll now = start + (end - start) / 2;
    ll cnt = 0;
    for (int i = 0; i < N; i++){
      ll res = H[i] - now * B;
      if (res > 0){
        cnt += res / (A - B);
        if (res % (A - B) != 0) cnt++;
      }
    }

    if (now >= cnt){
      result.push_back(make_pair(now, true));
      end = now;
    }else{
      result.push_back(make_pair(now, false));
      start = now;
    }
    if (end - start == 1) C++;
  }

  sort(result.begin(), result.end());

  for (int i = 0; i < result.size() - 1; i++){
    if (result[i].second == false && result[i + 1].second == true){
      cout << result[i].first + 1 << endl;
      break;
    }
    
  }
  
  

  return 0;
}


Measured memory_bytes: 1024
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    // a0 < a1
    // b0 > b1
    // a0+b0 > a1+b1
    //b0-b1 > a1-a0
    let n: usize = sc.read();
    let mut p = vec![];
    for _ in 0..n {
        p.push(sc.read::<usize>() - 1);
    }

    let cc = 30000;
    let mut a = vec![0; n];
    for i in 0..n {
        a[i] = (1 + cc * i) as i64;
    }
    let mut b = vec![0i64; n];
    for i in 1..n {
        let (p, q) = (p[i - 1], p[i]);
        if p < q {
            // ap < aq
            // bp > bq
            // ap+bp < aq+bq
            // bp-bq < aq-ap
            //            eprintln!("b[{p}]-b[{q}] < a[{q}]-a[{p}]", p = p, q = q);
            b[q] = b[p] - (a[q] - a[p] - 1);
        } else {
            let (p, q) = (q, p);
            // ap < aq
            // bp > bq
            // ap+bp > aq+bq
            // bp-bq > aq-ap
            //            eprintln!("b[{p}]-b[{q}] > a[{q}]-a[{p}]", p = p, q = q);
            b[p] = b[q] + a[q] - a[p] + 1;
        }
    }

    let min_b = *b.iter().min().unwrap();
    for i in 0..n {
        b[i] += 1 - min_b;
    }

    for i in 0..n {
        if i > 0 {
            sc.write(" ");
        }
        sc.write(format!("{}", a[i]));
    }
    sc.write("\n");
    for i in 0..n {
        if i > 0 {
            sc.write(" ");
        }
        sc.write(format!("{}", b[i]));
    }
    sc.write("\n");
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4732
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean[] sCards = { true, true, true, true, true, true, true, true, true, true, true, true, true, };
        boolean[] hCards = { true, true, true, true, true, true, true, true, true, true, true, true, true, };
        boolean[] cCards = { true, true, true, true, true, true, true, true, true, true, true, true, true, };
        boolean[] dCards = { true, true, true, true, true, true, true, true, true, true, true, true, true, };
        StringBuilder sb = new StringBuilder();

        int restCardCnt = in.nextInt();
        while (in.hasNext()) {
            String suit = in.next();
            int number = in.nextInt();

            for (int i = 0; i < restCardCnt; i++) {
                if (suit.equals("S")) {
                    sCards[number - 1] = false;
                } else if (suit.equals("H")) {
                    hCards[number - 1] = false;
                } else if (suit.equals("C")) {
                    cCards[number - 1] = false;
                } else {
                    dCards[number - 1] = false;
                }
            }
        }

        printRestCards("S", sCards, sb);
        printRestCards("H", hCards, sb);
        printRestCards("C", cCards, sb);
        printRestCards("D", dCards, sb);

        System.out.print(sb.toString());
    }

    private static void printRestCards(String suit, boolean[] rest, StringBuilder sb) {
        for (int i = 0; i < rest.length; i++) {
            sb.append(rest[i] ? suit + " " + (i + 1) + "\n" : "");
        }
        return;
    }
}

Measured memory_bytes: 18108
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
 
typedef long long ll;
 
using namespace std; 
 
#define REP(inc, bgn, end) for (int inc = bgn; inc < end; inc++)

int main() {
    float n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
    } else if (int(n) % 2 == 0) {
        cout << 0.5 << endl;
    } else {
        cout << ((n + 1) / 2) / n << endl;
    }
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return res;
}
struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

modint dp[3001][3001];
void solve() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	dp[a][b] = 1;
	Rep(i, a, c) {
		modint sum = 0;
		Rep1(j,b, d) {
			sum *= i;
			dp[i + 1][j] += dp[i][j] * (modint)j;
			dp[i + 1][j] += sum;
			sum += dp[i][j];
		}
	}
	//cout << dp[2][1] << " " << dp[2][2] << "\n";
	modint sum = 0;
	Rep1(j, b, d) {
		sum *= c;
		sum += dp[c][j];
	}
	cout << sum << "\n";
}


signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)
		solve();
	stop
		return 0;
}


Measured memory_bytes: 90336
#include <iostream>
#include <climits>
using namespace std;
#define ll long long
void solve(){
	string s,t;
	cin >> s >> t;
	ll n=s.size(),m=t.size();
	ll dp[n+1][m+1];
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=m;j++){
			if(!i || !j){
				dp[i][j]=0;
			}
			else{
				if(s[i-1]==t[j-1]){
					dp[i][j]=dp[i-1][j-1]+1;
				}
				else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
	}
	ll length=dp[n][m];
	string ans="";
	ll i=n,j=m;
	while(length){
		if(s[i-1]==t[j-1]){
			ans=s[i-1]+ans;
			i--;
			j--;
			length--;
		}
		else{
			if(dp[i-1][j]>dp[i][j-1]){
				i--;
			}
			else{
				j--;
			}
		}
	}
	cout << ans << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t=1;
	// cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 73968
import java.util.Scanner;

public class Main {
    void run(String[] args){
        Scanner scan=new Scanner(System.in);
        Integer m=scan.nextInt();
        Integer time=scan.nextInt();
        Integer speed=scan.nextInt();
        if(m<=time*speed){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
    public static void main(String args[]){
        Main printer = new Main();
        printer.run(args);
    }
}

Measured memory_bytes: 35692
#include <bits/stdc++.h>
#define endl "\n"
#include <set>


using namespace std;
int main(){
    
ios_base::sync_with_stdio(false);
    cin.tie(NULL);    
int n,k;
cin>>n>>k;
vector <int> a;
for (int i=0; i<n; i++)
{
	int temp; cin>>temp;
	a.push_back(temp);
}

bool states[k+1];
for (int i=0; i<k+1; i++)

	{states[i]=0; }
	
for (int j=0; j<n; j++)
{
	states[a[j]]=1;
}

for (int i=1; i<k+1; i++)
{
	if (states[i]==1) {continue; }
	else
	{
	bool x=1;
	for (int j=0; j<n; j++)
	{
		if (i-a[j]>=0)
		{ x= x & states[i-a[j]]; 
		}
	}
	if (x==1) {states[i]=0; }
	else {states[i]=1;}
	}
}

if (states[k]==0) {cout<<"Second"<<endl;}
else {cout<<"First"<<endl;}
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(){
	int A,B;
	cin>>A>>B;
	if(A+B>=A-B){
		if(A+B>=A*B){
			cout<<A+B<<endl;
		}else{
			cout<<A*B<<endl;
		}
	}else{
		if(A-B>=A*B){
			cout<<A-B<<endl;
		}else{
			cout<<A*B<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_N 50
#define MAX 50001
#define INF 1e9
int n, c[MAX_N];

int getNum(){
  int cost[MAX];

  memset(cost,0,sizeof(cost));
  cost[0] = 1;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < MAX-c[i] ; j++){
      cost[c[i]+j] += cost[j];
    }
  }

  for(int i = 0 ; i < MAX ; i++){
    if(cost[i] == 0){
      return 1;
    }
  }

  fill(cost,cost+MAX,INF);
  cost[0] = 0;
  for(int i = 0 ; i < n ; i++){
    for(int j = c[i] ; j < MAX ; j++){
      cost[j] = min(cost[j], cost[j-c[i]]+ 1);
    }
  }

  int s = MAX-1;
  for(int i = s ; i >= 1 ; i--){
    int rem = i, cnt = 0;
    for(int j = n-1 ; j >= 0 ; j--){
      if(rem >= c[j]){
        cnt += rem / c[j];
        rem %= c[j];
      }
    }
    if(cost[i] != cnt){
      return 2;
    }
  }

  return 3;
}

int main(){
  int Tc = 1;

  while(scanf("%d" ,&n), n){
    for(int i = 0 ; i < n ; i++){
      scanf("%d" , c+i);
    }

    int num = getNum();

    printf("Case #%d: " ,Tc++);
    if(num == 1){
      puts("Cannot pay some amount");
    }else if(num == 2){
      puts("Cannot use greedy algorithm");
    }else{
      puts("OK");
    }
  }

  return 0;
}

Measured memory_bytes: 1396
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision

#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL  MOD=1E9+7;

struct Problem{
    long long pow_(long long a, long long n){
        long long i=1,ret=1,p=a;
        while(i<=n){
            if(i&n) ret*=p;
            i=(i<<1);
            p*=p;
        }
        return ret;
    }
    void solve(){
        vector<LL> ans,q;
        for(LL i=0,j=1; i<=9; ++i,++j){
            char tmp;
            cout << "? " << j <<"\n";
            q.push_back(j);
            cout <<flush;
            cin >> tmp;
            ans.push_back(tmp=='Y'?1:0);
            j=j*10-1;
            cout << "? " << j <<"\n";
            q.push_back(j);
            cout <<flush;
            cin >> tmp;
            ans.push_back(tmp=='Y'?1:0);
        }
        DBG(ans,q)
        int dig=0;
        if(ans[18]){
            LL ret=1e9;
            for(int i=8; i>=0; --i){
                if(ans[2*i+1]){
                    ret/=10;
                }else{
                    break;
                }
            }
            cout << "! " << ret <<"\n";
        }else{
            for(int i=8; i>=0; --i){
                if(ans[2*i]){
                    dig=i+1;
                    break;
                }
            }
            LL ub=pow_(10,dig)-1,lb=pow_(10,dig-1);
            while(ub-lb>1){
                LL mid=(ub+lb)/2;
                if(check(mid*10)) ub = mid;
                else lb=mid;
            }
            cout << "! " <<ub <<"\n";
        }

    }
    bool check(LL mid){
        cout << "? "<<mid <<"\n";
        cout << flush;
        char tmp;
        cin >> tmp;
        return tmp=='Y';
    }
};

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

    Problem p;
    p.solve();
    return 0;
}



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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
	int n;
	cin >> n;
	vector<ll> t(n);
	rep(i, n) cin >> t[i];
	ll ans = t.back();
	rep(i, n - 1) ans = lcm(ans, t[i]);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from functools import reduce
from itertools import permutations

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

def find_dist(fr: int, to: int):
    return graph[fr][to]

n,m,rn = li()
r = list(li_())
adj_list = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    adj_list[a].append((c, b))
    adj_list[b].append((c, a))
    
graph = [[0]*rn for _ in range(rn)]
for i, ri in enumerate(r):
    dist = dijkstra(adj_list, n, ri)
    for j, rj in enumerate(r):
        graph[i][j] = dist[rj]

ans = float('inf')
for route in permutations(range(len(r)), len(r)):
    cand = 0
    for i,j in zip(route[:-1], route[1:]):
        cand += graph[i][j]
    
    ans = min(ans, cand)

print(ans)


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

int main() {
  int x;
  cin >> x;
  if (x >= 30) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3580
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define endl '\n'
#define fi first
#define se second



using namespace __gnu_pbds;
using namespace std;
 const int mod=1e9+7;
// const int mod=998244353;
const int INF=4e18+10;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define readv(x, n) vector<int> x(n); for(auto &i:x) cin>>i; 


int pow(int a, int b)
{
    int prod=1;
    int mult=a%mod;
    while(b!=0)
    {
        if(b%2)
        {
            prod*=mult;
            prod%=mod;
        }
        mult*=mult;
        mult%=mod;
        b/=2;
    }
    return prod;
}
int mod_inv(int q, int mod)
{
    return pow(q, mod-2);
}
const int MAXN=2e5;
std::vector <int> prime;
bool is_composite[MAXN];
int phi[MAXN];

void sieve (int n) {
    std::fill (is_composite, is_composite + n, false);
    phi[1] = 1;
    for (int i = 2; i < n; ++i) {
        if (!is_composite[i]) {
            prime.push_back (i);
            phi[i] = - 1;                 //i is prime
        }
        for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
            is_composite[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = 0;  //prime[j] divides i
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]]; //prime[j] does not divide i
            }
        }
    }
}

signed main()

{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
       cout.tie(NULL);
     #ifndef ONLINE_JUDGE
        if(fopen("INPUT.txt","r"))
        {
        freopen ("INPUT.txt" , "r" , stdin);
        freopen ("OUTPUT.txt" , "w" , stdout);
        }
     #endif
    auto clk=clock(); 
    // -------------------------------------Code starts here---------------------------------------------------------------------     
 
    int n;
    cin>>n;
    readv(a,n);


    vector<int> sasti_dp(n+10, -INF);

    vector<int> dp(n+10, -INF);
    dp[0]=a[0];
    dp[1]=max(a[0], a[1]);

    sasti_dp[0]=0;

    int alter_sum=a[0];
    for(int i=2;i<n;i++)
    {
        if(i%2==0)
        {
        sasti_dp[i]=max(sasti_dp[i-2] +a[i], dp[i-1] );
        dp[i]=max(dp[i-1], sasti_dp[i-2]+a[i]);
        alter_sum+=a[i];
        }
        else
        {
            dp[i]=max(alter_sum, a[i]+ dp[i-2]);
        }

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

    // -------------------------------------Code ends here------------------------------------------------------------------


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    return 0;
 }


Measured memory_bytes: 8012
N,M=map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
ans=0
#print(AB)
for i in range(N):
    if M>=AB[i][1]:
        M-=AB[i][1]
        ans+=AB[i][0]*AB[i][1]
    else:
        ans+=AB[i][0]*M
        M=0
    if M<=0:
        break
print(ans)

Measured memory_bytes: 27884
def fact2(a, b):
    c2 = 0
    c5 = 0
    while a%2 == 0:
        a //= 2
        c2 += 1
    while a%5 == 0:
        a //= 5
        c5 += 1
    return min(c2-b, 9), min(c5-b,9)

def main():
    N = int( input())
    A2 = [0]*N
    A5 = [0]*N
    AS = [0]*N
    for i in range(N):
        a = input()
        if '.' in a:
            b, c = a.split('.')
            if int(c) == 0:
                pass
            else:
                AS[i] = len(c)
                b += c
        else:
            b = a
        # A2[i], A5[i] = fact( int(b))
        # print(b)
        A2[i], A5[i] = fact2( int(b), AS[i])

    R = [ [0]*19 for _ in range(19)]
    for i in range(N):
        a, b = A5[i]+9, A2[i]+9
        R[a][b] += 1
    AR = [ [0]*19 for _ in range(19)]
    for i in range(18,-1,-1):
        for j in range(17,-1,-1):
            R[i][j] = R[i][j] + R[i][j+1]
    for j in range(19):
        for i in range(17,-1,-1):
            R[i][j] += R[i+1][j]
    ans = 0
    # print("\n".join( [" ".join( map( str, a)) for a in AR]))
    for k in range(N):
        i, j = A5[k], A2[k]
        if i <= 9 and j <= 9:
            ans += R[-i+9][-j+9]
            # print(-i+9,-j+9)
        if AS[k] == 0:
            ans -= 1
    print(ans//2)

# 2
# 10.73741824 
# 3051.7578125
# 2**30, 2**15

if __name__ == '__main__':
    main()


Measured memory_bytes: 80044
import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		while (sc.hasNext()) {
			out.println(RomanToArabic(sc.next()));
		}
	}
	static int RomanToArabic (String s) {
		String[] a = {"IV","IX","XL","XC","CD","CM"};
		String[] b = {"IIII","VIIII","XXXX","LXXXX","CCCC","DCCCC"};
		for (int j=0; j<6; j++) {
			s = s.replaceAll(a[j],b[j]);
		}
		int n = 0;
		int[] number = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
		String[] roma = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
		for (int i=0; i<s.length(); i++) {
			for (int j=0; j<13; j++) {
				if (s.substring(i,i+1).equals(roma[j])) {n += number[j];}
			}
		}
		return n;
	}

}


Measured memory_bytes: 26192
#!/usr/bin/perl
#= CPAN mocules =====================================================#
use strict;				# strictモード
use warnings;			# 警告有効

#= Global values ====================================================#
#= Local routines ===================================================#
sub main(){
	my $in = <>;chomp $in;
	my ($d, $n) = split(/ /, $in);

	$d = 100 ** $d;
	if (($n % 100) == 0){
		$n++;
	}
	print $d * $n;
	print "\n";



	return 0;
}

#----- 実行 -----#
exit( main() );




Measured memory_bytes: 640
S = input()
n = [0] * len(S)

c = 0
ev = 0
od = 0
for i in range(len(S)):
    if S[i] == 'R':
        c += 1
        if c & 1:
            ev += 1
        else:
            od += 1
    else:
        n[i] += od
        n[i-1] += ev
        c, ev, od = 0, 0, 0

S = S[::-1]
n.reverse()

c = 0
ev = 0
od = 0
for i in range(len(S)):
    if S[i] == 'L':
        c += 1
        if c & 1:
            ev += 1
        else:
            od += 1
    else:
        n[i] += od
        n[i-1] += ev
        c, ev, od = 0, 0, 0

n.reverse()

print(*n)






Measured memory_bytes: 6400
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
#define rep2(x,from,to) for(int x = (from); x < (to); ++(x))
#define rep(x,to) rep2(x,0,to)

void clear(int r, int c, string &b) {
	if(b[r * 8 + c] == '0') return;
	else {
		b[r * 8 + c] = '0';
		rep2(i,1,4) {
			if(r+i < 8) clear(r+i,c,b);
			if(r-i >= 0) clear(r-i,c,b);
			if(c+i < 8) clear(r,c+i,b);
			if(c-i >= 0) clear(r,c-i,b);
		}
	}
}
int main() {
	int n;
	cin >> n;
	rep(i,n) {
		string s, t;
		rep(j,8) {
			cin >> t;
			s += t;
		}
		int r, c;
		cin >> c >> r;
		c--,r--;
		clear(r,c,s);
		cout << "Data " << i+1 << ":" << endl;
		rep(j,8) {
			rep(k,8) {
				cout << s[j * 8 + k];
			}
			cout << endl;
		}
	}
	return 0;
}

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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ '0');
	return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MAXN = (int) 2e5;

// Template-Libs

// END

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

inline bool check(int m)
{
	if(m == 1)
	{
		for(int i = 2; i <= n; ++i) if(a[i] <= a[i - 1]) return 0;
		return 1;
	}

	static map<int, int> d;
	d.clear();

	for(int i = 2; i <= n; ++i) if(a[i] <= a[i - 1])
	{
		d.erase(d.upper_bound(a[i]), d.end());
		++d[a[i]];
		for(int k = a[i]; k && d[k] == m; --k) d.erase(k), ++d[k - 1];
		if(d.find(0) != d.end()) return 0;
	}
	return 1;
}

inline void solve()
{
	int l = 1, r = n;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", r);
}

int main()
{
	input();
	solve();

	return 0;
}



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

int main(){
    
    int h,w,mod=1000000007;
    cin>>h>>w;
    char a[h+2][w+2];
    long long int dp[h+2][w+2];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>a[i][j];
            dp[i][j]=0;
        }
    }
    
    dp[1][1]=1;
    for(int i=2;i<=w;i++){
        if(a[i][1]=='#')
        break;
        else
        dp[i][1]=1;
    }
    
    for(int i=2;i<=w;i++){
        if(a[1][i]=='#')
        break;
        else
        dp[1][i]=1;
    }
    for(int i=2;i<=h;i++){
        for(int j=2;j<=w;j++){
            
            if(a[i][j] == '.')
            {
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            
            }
            else{
                dp[i][j]=0;
            }
        }
    }
    cout<<dp[h][w];
}

Measured memory_bytes: 9088
N, T = map(int, input().split())
min_c = 1001
for n in range(N):
    c, t = map(int, input().split())
    if t <= T:
        min_c = min(min_c, c)

if min_c != 1001:
    print(min_c)
else:
    print('TLE')

Measured memory_bytes: 2940
#include <iostream>
#include <string>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  string s;
  cin >> s;
  for (int i = 1; i <= s.size(); i++) {
    if (i % 2 != 0) {
      cout << s[i - 1];
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll cd = 1000000007;
const double pi = 3.14159265358979;

int main() {
    ll N;
    str s;
    cin >> N >> s;
    ll countr = 0, countb = 0;
    rep(i, N) {
        if(s.at(i) == 'R') {
            countr++;
        }
        else {
            countb++;
        }
    }
    if(countr > countb) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

int main()
{
    string s;
    int counter;
    cin >> s;
    if (s[0] == '1') ++counter;
    if (s[1] == '1') ++counter;
    if (s[2] == '1') ++counter;
    cout << counter << endl;
    return 0;
}

Measured memory_bytes: 256