akhauriyash/Code-Regression huggingface dataset:
/*
 Remember not to use arithmetic operation in double while comparision 

 priority of uses
 array > maps > unordered_maps
*/

#include<bits/stdc++.h>
#define lli long long int
#define vl vector<lli>
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define pll pair<lli,lli>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n,w;
	cin>>n>>w;
	vl wt(n),val(n);
	for(int i=0;i<n;i++)
	cin>>wt[i]>>val[i];

	lli DP[n+1][w+1];
	for(int i=0;i<=w;i++)
	DP[0][i]=0;
	for(int i=0;i<=n;i++)
	DP[i][0]=0;

	for(lli i=1;i<=n;i++)
	{
		for(lli j=0;j<=w;j++)
		{
			if(wt[i-1]>j)
				DP[i][j]=DP[i-1][j];
			else
				DP[i][j]=max(val[i-1]+DP[i-1][j-wt[i-1]],DP[i-1][j]);
		}
	}
	cout<<DP[n][w];
	return 0;
}


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

//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
//typedef unsigned long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
typedef pair<int, int> P;
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 100;
//const ll INF = (1ll << 31) - 1;
const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

//bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;

class CumulativeSum {
    vector<ll> numbers;
    vector<ll> sums;

public:
    CumulativeSum(int n) {
        numbers.resize(n);
        sums.resize(n);
    }

    void set(int i, ll value) {
        numbers[i] = value;
    }

    ll getSum(int i) {
        if (i == -1) return 0;
        if (i == sums.size()) return 0;
        return sums[i];
    }

    ll getSectionSum(int start, int end) {
        return getSum(end) - getSum(start - 1);
    }

    void calculate() {
        for (int i = 0; i < numbers.size(); i++) {
            sums[i] = getSum(i - 1) + numbers[i];
        }
    }

};


int main() {
    int n;
    cin >> n;
    vector<ll> numbers(n);
    rep(i, n)cin >> numbers[i];

    CumulativeSum cs(n);
    rep(i, n) cs.set(i, numbers[i]);
    cs.calculate();

    ll ans = INF;
    for (int i = 0; i < n - 1; i++) {
        ll s = cs.getSum(i);
        ll a = cs.getSectionSum(i + 1, n - 1);
        ll now = abs(s - a);
        cmin(ans, now);
    }
    cout << ans << endl;

}



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

/*
二次元で面積の場合を考えると、面積が最大になるのはx = L/2のとき
これは微分したら出る。

三次元の場合は、先に一辺xを設定すると、体積が最大になるのは残りの二辺が (L-x) / 2のとき。
この元で体積を計算して微分すると、(L-3x)(L-x) = 0が導ける。
よって、x= L or L / 3のとき、最大値。
x < Lより、x = L / 3で、残りの二辺も自動的にL/3となる。
*/

int main() {
    double L;
    cin >> L;
    cout << fixed << setprecision(7) << (L / 3.0) * (L / 3.0) * (L / 3.0) << endl;
}

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

int main() {
	int n,m;
	cin >> n >> m;
	vector<int> h(n,0),g(n,0);
	for(int i=0;i<n;i++)
	{
		cin >> h.at(i);
	}
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin >> a >> b;
		if(h.at(a-1) > h.at(b-1))
		{
			g.at(b-1)++;
		}
		else if(h.at(a-1) < h.at(b-1))
		{
			g.at(a-1)++;
		}
		else
		{
			g.at(a-1)++;
			g.at(b-1)++;
		}
	}
	int k=0;
	for(int i=0;i<n;i++)
	{
		if(g.at(i) == 0)
		{
			k++;
		}
	}
	cout << k << endl;
	return 0;
}


Measured memory_bytes: 3992
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int main(){
  string S;
  cin >> S;
  vector<bool> alpha(26, false);
  bool ret = true;
  for(int i=0; i<S.size(); i++){
    if(!alpha[(int)S[i] - (int)'a'])
      alpha[(int)S[i] - (int)'a'] = true;
    else{
      ret = false;
      break;
    }
  }
  if(ret)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

int main(){
    int n,m; cin >> n >> m;
    map<int,int> ma;
    rep(i,n){
        int k; cin >> k;
        rep(j,k){
            int x; cin >> x; x--;
            ma[x]++;
        }
    }
    int ans = 0;
    rep(i,m) if(ma[i] == n) ans++;
    cout << ans << endl;
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > q;
    rep(i, n) {
        int a;
        cin >> a;
        q.push(a);
    }
    while (q.size() > 1) {
        int m = q.top();
        q.pop();
        rep(i, q.size()) {
            int a = q.top();
            q.pop();
            if (a % m != 0) {
                a %= m;
                q.push(a);
            }
        }
        q.push(m);
    }
    cout << q.top() << endl;
}

Measured memory_bytes: 3860
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;

int main() {
	int N;
	cin >> N;
	map<int, int> cnt;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		cnt[A]++;
	}
	ll ans = 1;
	if (N % 2 == 0) {
		for (int i = 1; i <= N - 1; i += 2) {
			if (cnt[i] != 2) {
				ans = 0;
				break;
			}
			(ans *= 2) %= MOD;
		}
	}
	else {
		if (cnt[0] != 1) ans = 0;
		for (int i = 2; i <= N - 1; i += 2) {
			if (cnt[i] != 2) {
				ans = 0;
				break;
			}
			(ans *= 2) %= MOD;
		}
	}
	cout << ans << endl;
}


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

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

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

int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> cnt(41,0);
    for (int i = 0;i < n;++i) {
        ll a;
        cin >> a;
        for (int j = 0;j < 40;++j) if ((a>>j)&1) cnt[j]++;
    }
    vector<ll> dp0(41,0),dp1(41,0);
    for (int i = 39;i >= 0;--i) {
        if ((k>>i)&1) {
            dp0[i] = dp0[i+1]+(1LL<<i)*(n-cnt[i]);
            dp1[i] = dp0[i+1]+(1LL<<i)*cnt[i];
        } else {
            dp0[i] = dp0[i+1]+(1LL<<i)*cnt[i];
        }
        if (dp1[i+1]) dp1[i] = max(dp1[i],dp1[i+1]+(1LL<<i)*max(n-cnt[i],cnt[i]));
    }
    cout << max(dp0[0],dp1[0]) << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
ans = 1
mians = 1
mians2 = 1
for i in range(N):
    ans *= 10
    ans %= 10 ** 9 + 7
for i in range(N):
    mians *= 9
    mians %= 10 ** 9 + 7
for i in range(N):
    mians2 *= 8
    mians2 %= 10 ** 9 + 7
mians = mians * 2 - mians2
if mians < 0:
    mians += 10 ** 9 + 7
mians %= 10 ** 9 + 7
ans -= mians
if ans < 0:
    ans += 10 ** 9 + 7
print(ans)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pl;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
#define SHOW(x) cout << #x << ": " << x << endl;
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){   
   int k,x;
   cin>>k>>x;
   if(k * 500 >= x)cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <climits>
#include <cmath>
#include <utility>
#include <vector>

#define MAX 10010

using namespace std;

int C[MAX] = {0};

void printArr(vector<int> &A, int n)
{
  for(int i = 0; i < n-1 ; i++) cout << A[i] << " ";
  cout << A[n-1] << endl;
}

int partition(vector<int> &A, int p, int r)
{
  int x = A[r];
  int i = p-1;
  int tmp;
  for(int j = p; j < r; j++)
  {
    if(A[j] <= x)
    {
      i++;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;
  return i+1;
}

int main()
{
  int n;
  vector<int> A;
  cin >> n;
  A.resize(n+1);
  for(int i = 0; i < n; i++) cin >> A[i];
  int pv =  partition(A,0,n-1);
  for(int i = 0; i < n; i++)
    printf("%s%d%s%s",(i==pv?"[":""),A[i],(i==pv?"]":""),(i==n-1?"\n":" "));
  return 0;
}

Measured memory_bytes: 1532
n = int(input())
s = input()

a = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

z = ''
for ss in s:
  for i in range(len(a)):
    if ss == a[i]:
      if i+n > 25:
        j = i+n -26
        z += a[j]
      else:
        z += a[i+n]

print(z)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    vector<lint> A(N);
    REP(i, N) cin >> A[i];
    vector<lint> num(N);
    vector<lint> cnt(N*2);
    IREP(i, N) {
        lint tmp = A[i] + (N-1 - i);
        if(tmp < N*2 && tmp >= 0) cnt[tmp]++;
        num[i] = cnt[N - i];
    }
    lint ans = 0;
    REP(i, N) {
        lint tmp = i + A[i] + 1;
        if(tmp >= N) continue;
        ans += num[tmp];
    }
    cout << ans << endl;
}

Measured memory_bytes: 9536
class Dice(list):
    def __init__(self, *args):
        super().__init__(*args)

    def roll(self, command):
        if command == 'N':
            self[0], self[1], self[5], self[4] = self[1], self[5], self[4], self[0]
        elif command == 'S':
            self[0], self[1], self[5], self[4] = self[4], self[0], self[1], self[5]
        elif command == 'W':
            self[0], self[3], self[5], self[2] = self[2], self[0], self[3], self[5]
        elif command == 'E':
            self[0], self[3], self[5], self[2] = self[3], self[5], self[2], self[0]

    def spin(self, repeat=1):
        for _ in range(repeat):
            self[3], self[1], self[2], self[4] = self[1], self[2], self[4], self[3]

    def _fix_position(self):
        self._min_num_to_top()
        self._min_side_num_to_front()

    def _min_num_to_top(self):
        idx = self.index(min(self))
        if idx == 0:
            pass
        elif idx == 1:
            self.roll('N')
        elif idx == 2:
            self.roll('W')
        elif idx == 3:
            self.roll('E')
        elif idx == 4:
            self.roll('S')
        elif idx == 5:
            self.roll('N')
            self.roll('N')

    def _min_side_num_to_front(self):
        idx = self.index(min(self[3], self[1], self[2], self[4]))
        if idx == 1:
            pass
        elif idx == 2:
            self.spin(1)
        elif idx == 3:
            self.spin(3)
        elif idx == 4:
            self.spin(2)

    def __hash__(self):
        self._fix_position()
        return hash(tuple(self))

    def __eq__(self, other):
        return hash(self) == hash(other)


if __name__ == '__main__':
    n = int(input())
    dices = set(Dice(map(int, input().split())) for _ in range(n))
    print('Yes' if n == len(dices) else 'No')

Measured memory_bytes: 6820
import  numpy   as      np

I_N             =       int(input())
S               =       input().split()
I_S             =       np.array(S).astype(type(I_N))
I_Counter       =       0

for i in range(1,I_N-1):

        if(I_S[i-1] < I_S[i] and I_S[i] < I_S[i+1]):
                I_Counter       +=      1
        elif(I_S[i-1] > I_S[i] and I_S[i] > I_S[i+1]):
                I_Counter       +=      1

print(I_Counter)



Measured memory_bytes: 12508
#include <iostream>

int A[1000000], n, q;
typedef long long ll;

using namespace std;

int binarySearch(int key){
    int left = 0;
    int right = n;
    int mid;

    while(left<right){
        mid = (left+right)/2;
        if(key==A[mid])return 1;
        if(key>A[mid])left = mid + 1;
        else if (key<A[mid]) right = mid;
    }
    return 0;
}

int main() {
    int k, sum = 0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> k;
        if(binarySearch(k))sum++;
    }
    cout << sum << "\n";

    return 0;
}


Measured memory_bytes: 3468
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K, A, B;
  cin >> K >> A >> B;
  string ans = "NG"; 

  for(int i=A; i<=B; i++){
    if(i%K==0){
      ans = "OK";
      break;
    }
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a, b;
    cin >> a >> b;
    
    if(a%3 ==0 || b%3 == 0 || (a+b)%3 == 0){
        cout << "Possible" << endl;
    }
    else{
        cout << "Impossible" << endl;
    }
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;

int A,B,Q;

signed main(){
    cin>>A>>B>>Q;
    vint S,T;
    S.pb(-INF);
    T.pb(-INF);
    rep(i,A){
        int a;cin>>a;S.pb(a);
    }
    rep(i,B){
        int a;cin>>a;T.pb(a);
    }
    S.pb(INF);T.pb(INF);

    while(Q--){
        int x;cin>>x;

        int ans=INF;
        int k=lower_bound(all(S),x)-S.begin();

        int a=S[k-1];
        int b=S[k];

        k=lower_bound(all(T),x)-T.begin();
        int c=T[k-1];
        int d=T[k];


        rep(i,2){
            rep(j,2){
                rep(k,2){
                    chmin(ans,abs(x-a)+abs(a-c));
                    swap(c,d);
                }
                swap(a,b);
            }
            swap(a,c);swap(b,d);
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3060
import java.io.PrintWriter;
import java.util.Scanner;

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

		int N = sc.nextInt();
		int[] h = new int[N];
		for (int i = 0; i < N; i++) {
			h[i] = sc.nextInt();
		}

		
		int[] cost= new int[N];
		cost[N-1] =0;
		for(int i=N-2; i>=0;i--) {
			if(i == N-2)cost[i]=Math.abs(h[i+1]-h[i]);
			else {
				cost[i] = Math.min(cost[i+1]+Math.abs(h[i+1]-h[i]), cost[i+2]+Math.abs(h[i+2]-h[i]));
			}				
		}
		pw.println(cost[0]);
		// end

		sc.close();
		pw.close();
	}
}


Measured memory_bytes: 49264
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

ll n, d, x, y;
int ans;

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> n >> d;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		if (x*x + y * y <= d * d)ans++;
	}
	cout << ans << endl;
}

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

long calc(long h) {
    if (h == 1) {
        return 1;
    }
    
    long count = 0;
    count = 2 * calc(h / 2) + 1;
    return count;
}

int main() {
    long h;
    cin >> h;
    long result = 0;
    
    result = calc(h);
    
    cout << result << endl;
}


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

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long 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 {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=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 {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};
int main(){
    int n,k;cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    vector<mint> cntmin(n),cntmax(n);
    combination c(100005);
    rep(i,n){
        if(i<=n-k)cntmin[i]=c(n-i-1,k-1);
        if(i>=k-1)cntmax[i] = c(i,k-1);
    }
    mint ans = 0;
    rep(i,n){
        ans += (cntmax[i]-cntmin[i])*mint(a[i]);
    }

    cout << ans << endl;
    //rep(i,n) printf("%d %d\n",cntmin[i],cntmax[i]);
    

}

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

using i64 = int_fast64_t;
using f64 = double;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    string s;
    cin >> s;
    if (s.size() == 3) reverse(begin(s), end(s));
    cout << s << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

constexpr int mod = 1000000007;
struct ModInt {
    ll x;
    ModInt (ll a) : x((a % mod + mod) % mod) {}
    ModInt operator- () const {
        return ModInt(-x);
    }
    ModInt &operator+= (const ModInt &a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-= (const ModInt &a) {
        if ((x -= a.x) < 0) x += mod;
        return *this;
    }
    ModInt &operator*= (const ModInt &a) {
        (x *= a.x) %= mod;
        return *this;
    }
    ModInt operator+ (const ModInt &a) const {
        ModInt res(*this);
        return res += a;
    }
    ModInt operator- (const ModInt &a) const {
        ModInt res(*this);
        return res -= a;
    }
    ModInt operator* (const ModInt &a) const {
        ModInt res(*this);
        return res *= a;
    }
    ModInt pow(ll t) const {
        if (!t) return 1;
        ModInt a = pow(t / 2);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    ModInt inv() const {
        return pow(mod - 2);
    }
    ModInt &operator/= (const ModInt &a) {
        return (*this) *= a.inv();
    }
    ModInt operator/ (const ModInt &a) const {
        ModInt res(*this);
        return res /= a;
    }
    friend ostream &operator<< (ostream &os, const ModInt &a){
        os << a.x;
        return os;
    }
};

vector<ModInt> fact, ifact;
void init(int N) {
    ModInt now(1);
    fact.push_back(now);
    for (int i = 1; i <= N; ++i) {
        ModInt M(i);
        now *= M;
        fact.push_back(now);
    }
    rep(i, N + 1) ifact.push_back(fact[i].inv());
}
ModInt comb(int x, int y) {
    if (x < y) return ModInt{0};
    else return fact[x] * ifact[y] * ifact[x - y];
}

int main() {
    int K;
    string S;
    cin >> K >> S;
    
    int N = SZ(S);
    ModInt ans(0), A(25), B(26);
    init(N + K);
    rep(i, K + 1) {
        ans += comb(N + K - i - 1, N - 1) * A.pow(K - i) * B.pow(i);
    }
    cout << ans << "\n";
    return 0;
}


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

int main()
{
    int i, N, K;
    double ans = 0;
    cin >> N >> K;
    vector<double> p(N);
    vector<double> S(N + 1);
    vector<double> q(N - K + 1);
    for (i = 0; i < N + 1; i++)
    {
        S.at(i) = 0;
    }
    for (i = 0; i < N; i++)
    {
        cin >> p.at(i);
        p.at(i) = (1 + p.at(i)) / 2.;
        S.at(i + 1) = S.at(i) + p.at(i);
    }
    for (i = 0; i < N - K + 1; i++)
    {
        q.at(i) = S.at(i + K) - S.at(i);
        if (ans <= q.at(i))
        {
            ans = q.at(i);
        }
    }
    cout << fixed << setprecision(15) << ans << endl;
}

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

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (i % 2 == 1 && s.c_str()[i] == 'R') {
            cout << "No" << endl;
            return 0;
        } else if (i % 2 == 0 && s.c_str()[i] == 'L') {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, M, X[10] = { 100, 2, 5, 5, 4, 5, 6, 3, 7, 6 }, DP[10010] = {}, INF = 1145141919;
	vector<int> V;
	cin >> N >> M;
	for (int i = 0; i <= N; i++) {
		DP[i] = -INF;
	}
	DP[0] = 0;
	for (int i = 0; i < M; i++) {
		int A;
		cin >> A;
		V.emplace_back(A);
	}
	sort(V.begin(), V.end(), greater<int>());
	for (int i = 1; i <= N; i++) {
		for (int j : V) {
			if (X[j] > i) continue;
			DP[i] = max(DP[i], DP[i - X[j]] + 1);
		}
	}
	int D = N;
	while (D != 0) {
		for (int j : V) {
			if (D >= X[j]) {
				if (DP[D - X[j]] == DP[D] - 1) {
					cout << j;
					D -= X[j];
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N,M = map(int, input().split())
#print(M)
S = list(map(int,input().split()))
S.sort(reverse=True)
#print(S)
L = len(S)
SUM = sum(S)
#print(SUM)
#print(L)
#print(S[M-1])
if S[M-1] / SUM >= 1/(4*M):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
N,K = map(int, input().split())
A_list = [0] + [int(e) for e in input().split()]

used_tele = 0
repeating_flag = False
moving_dict = dict() #key:街番号,value:テレポート回数
moving_dict[1]= 0
now_town = 1

while used_tele<K:
    next_town = A_list[now_town]
    used_tele += 1
    #print(used_tele,":",now_town,"→",next_town)
    
    if next_town in moving_dict:
        repeating_flag = True
        break
        
    moving_dict[next_town] = used_tele
    now_town = next_town
        
if repeating_flag == False:
    print(next_town)
else:
    moving_list = list(moving_dict.keys())
    repeating_start_town_index = moving_list.index(next_town)
    
    #print(moving_list)
    #print(moving_list[0:repeating_start_town_index])
    #print(moving_list[repeating_start_town_index:])
    
    repeating_moving_list = moving_list[repeating_start_town_index:]
    K -= len(moving_list[0:repeating_start_town_index])
    
    print(repeating_moving_list[K%len(repeating_moving_list)])

Measured memory_bytes: 33372
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const ll MAX = 1000010;
const ll MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
const ll ainf = 998244353;

struct cell {
	int x, y;
	int deep;
	cell(int x, int y, int deep) : x(x), y(y), deep(deep) {}
};

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

int W, H, N;
int X1[500], X2[500], Y1[500], Y2[500];

bool fld[500 * 6][500 * 6];
int compress(int* x1, int* x2, int w) {
	vector<int> xs;
	for (int i = 0; i < N; i++)
	{
		for (int d = -1; d <= 1; d++)
		{
			int tx1 = x1[i] + d, tx2 = x2[i] + d;
			if (1 <= tx1 && tx1 <= W) xs.push_back(tx1);
			if (1 <= tx2 && tx2 <= W) xs.push_back(tx2);
		}
	}

	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());

	for (size_t i = 0; i < N; i++)
	{
		x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
		x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
	}
	return xs.size();
}
const int MAX_N = 1 << 17;

void solv() {

	int n;
	cin >> n;
	ll h[100010];
	for (size_t i = 0; i < n; i++)
	{
		cin >> h[i];
	}
	ll ma = 0;
	for (int i = 0; i < n; i++)
	{
		if (ma > h[i] + 1) {
			cout << "No" << endl;
			return;
		}

		ma = max(ma, h[i]);
	}

	cout << "Yes" << endl;
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
        int n, m; cin >> n >> m;
        int WA[n+1];
        bool AC[n+1];
        int ACnum = 0, WAnum = 0;
        for (int x = 1; x <= n; ++x){
            WA[x] = 0;
            AC[x] = false;
        }
        while (m--){
            int p;
            string s;
            cin >> p >> s;
            if (AC[p]){
                continue;
            }
            if (s == "AC"){
                ACnum++;
                WAnum += WA[p];
                AC[p] = true;
            }
            else{
                WA[p]++;
            }
        }
        cout << ACnum << " " << WAnum << endl;
    return 0;
}


Measured memory_bytes: 4120
from sys import stdin
MOD = 1000000007
n, k = [int(x) for x in stdin.readline().rstrip().split()]

C = [ [0]*(2003) for _ in range(2003)]

for i in range(2003):
  C[i][0] = C[i][i] = 1
  for j in range(1, i):
      C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD

def solvedp(n, m):
    if n < m:
        return 0
    return C[n-1][m-1]

def solve(n,k,i):
    if n == k and i == 1:
      print(1)
      return
    ans = 0
    if i > 1:
      ans += solvedp(n-k, i-1)
    ans = (ans + solvedp(n-k, i))%MOD
    ans = (ans + solvedp(n-k, i))%MOD
    ans = (ans + solvedp(n-k, i+1))%MOD
    ans = (ans * solvedp(k, i))%MOD
    print(ans)

for i in range(k):
  solve(n,k,i+1)


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

typedef long long int ll;
typedef vector<int> vi;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pvec(v) for(auto e: v) cout << e << " ";
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i, a, b) for(int i = (a); i<(b); ++i)
#define pb push_back
#define INF 1000000005
#define MOD 1000000007
#define all(v) v.begin(), v.end()

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

ll power(ll x, ll y, ll p = MOD){  
    ll res = 1LL; 
    x = x % p;
    if (x == 0) return 0;
    while (y > 0){
        if (y & 1LL)  
            res = (res*x) % p;
        y = y>>1LL; 
        x = (x*x) % p;  
    }  
    return res;  
}  

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

	ll arr[n];
	for(int i = 0; i<n; ++i)
		cin >> arr[i];
	if(n == 1){
        cout << 0 << endl;
        return 0;
    } else if(n == 2){
        cout << arr[0] << endl;
        return 0;
    }
    
    sort(arr, arr + n, [](ll a, ll b){
        return a > b;
    });

    priority_queue<pair<ll, int>> q;
    q.push({arr[1], 0});
    q.push({arr[1], 1});

    ll sum = arr[0];
    for(int i = 2; i<n; ++i){
        pair<ll, int> curr = q.top(); q.pop();
        // cout << curr.first << " " << curr.second << endl;
        sum+=curr.first;
        q.push({arr[i], curr.second});
        q.push({arr[i], curr.second + 1});
    }

    cout << sum << endl;
	return 0;
}

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

 
int main() {
    int H, W;
    cin >> H >> W;
    char s[60][60];
    char ans[60][60];
    int dx[8] = {1,1,0,-1,-1,-1,0,1};
    int dy[8] = {0,1,1,1,0,-1,-1,-1};
    for(int i = 1; i <= H; i++)
        for(int j = 1; j <= W; j++)
            cin >> s[i][j];

    for(int i = 0; i < 60; i++)
        for(int j = 0; j < 60; j++)
            ans[i][j] = '#';
    
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            if(s[i][j] == '.'){
                char cnt = 0;
                for(int k = 0; k < 8; k++){
                    int i2 = i + dx[k];
                    int j2 = j + dy[k];
                    if(s[i2][j2] == '#'){
                        cnt++;
                    }
                }
                ans[i][j] = cnt + '0';
            }
        }
    }


    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            cout << ans[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3608
import sys

N, K = map(int, input().split())
Ds = list(input().split())

number = N-1
while True:
    number += 1
    ng = False
    for i in range(K):
        if Ds[i] in str(number):
            ng = True
            break

    if ng == False:
        print(number)
        sys.exit(0)


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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

vector<pair<Int, Int>> G[100001];
Int d[100001];

int main() {
    Int k;
    cin >> k;
    for (Int i = 1; i < k; i++) {
        if ((i + 1) % 10 != 0) {
            G[i].emplace_back((i + 1) % k, 1);
        }
        G[i].emplace_back(i * 10 % k, 0);
    }
    for (Int i = 0; i < (Int)k; i++) {
        d[i] = INF;
    }
    d[1] = 0;
    deque<Int> q;
    q.push_back(1);
    while (not q.empty()) {
        Int x = q.front();
        q.pop_front();
        for (Int i = 0; i < (Int)G[x].size(); i++) {
            Int to = G[x][i].first;
            Int cost = G[x][i].second;
            if (d[to] > d[x] + cost) {
                d[to] = d[x] + cost;
                q.push_back(to);
            }
        }
    }
    print(d[0] + 1);
    return 0;
}

Measured memory_bytes: 11556
n = int(input())
A = []
B = []
for i in range(n):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort(reverse=True)
if n % 2 == 1:
    mn = A[(n+1)//2-1] 
    mx = B[(n+1)//2-1]
    print(mx - mn + 1)
else:
    mn1 = A[(n+1)//2-1]
    mn2 = A[(n+1)//2]    
    mx1 = B[(n+1)//2]    
    mx2 = B[(n+1)//2-1]
    # print(mn1,mx1,mn2,mx2)
    print((mx2+mx1)-(mn1+mn2)+1)




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

namespace AtCoder.DP
{
    class EDPC_O
    {
        static int mod = 1000000007;

        public static void Main()
        {
            var n = int.Parse(Console.ReadLine());

            var a = new bool[n][];
            for (int i = 0; i < n; i++)
                a[i] = Console.ReadLine().Split(' ').Select(s => s == "1").ToArray();

            var bit = Enumerable.Range(0, n).Select(i => 1 << i).ToArray();

            var dp = new int[n + 1, 1 << n];
            dp[0, 0] = 1;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < 1 << n; j++)
                {
                    if (dp[i, j] == 0)
                        continue;

                    for (int k = 0; k < n; k++)
                    {
                        if (!a[i][k])
                            continue;
                        int l = j | bit[k];
                        if (l == j)
                            continue;
                        dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % mod;
                    }
                }
            }
            Console.WriteLine((dp[n, (1 << n) - 1] + mod) % mod);
        }
    }
}


Measured memory_bytes: 174944
n=int(input())
al=list(map(int,input().split()))

dic={}
for v in al:
    if not v in dic.keys():
        dic[v]=1
    else:
        dic[v]=dic[v]+1
count_l=[]
for v in range(min(al)-1,max(al)+2):
    count=0
    count=dic.get(v-1,0)+dic.get(v,0)+dic.get(v+1,0)
    count_l.append(count)
print(max(count_l))

Measured memory_bytes: 14008
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    double a, b;
    cin >> a >> b;
    cout << a/b;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    double ans=0;
    REP(i,N){
        double x; cin>>x;
        string u; cin>>u;
        if(u=="JPY") ans+=x;
        else ans+=380000*x;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
int fa[100005], arr[100005];
std::vector<int> vec[100005];
std::multiset<int> se;
int getfa(int u) { return u == fa[u] ? u : fa[u] = getfa(fa[u]); }
int main()
{
	// freopen("K.in", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	if (m == n - 1)
	{
		puts("0");
		return 0;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		se.insert(arr[i]);
		fa[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		fa[getfa(u)] = getfa(v);
	}
	for (int i = 0; i < n; i++)
		vec[getfa(i)].push_back(arr[i]);
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (vec[i].empty())
			continue;
		int x = *std::min_element(vec[i].begin(), vec[i].end());
		ans += x;
		se.erase(se.find(x));
	}
	for (int i = 0; i < n - m - 2; i++)
	{
		if (se.empty())
		{
			puts("Impossible");
			return 0;
		}
		ans += *se.begin();
		se.erase(se.begin());
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 11136
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

int main() {
    string s, t[3] = { "Sunny", "Cloudy", "Rainy" };
    cin >> s;
    cout << t[((find(t, t + 3, s) - t) + 1) % 3] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  K--;
  if(S[K] == 'A') S[K] = 'a';
  else if(S[K] == 'B') S[K] = 'b';
  else if(S[K] == 'C') S[K] = 'c';
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
N, L = map(int, input().split())
As = list(map(int, input().split()))

for iKnot in range(1, N):
    if As[iKnot - 1] + As[iKnot] >= L:
        print('Possible')
        for i in range(1, iKnot):
            print(i)
        for i in reversed(range(iKnot + 1, N)):
            print(i)
        print(iKnot)
        break
else:
    print('Impossible')


Measured memory_bytes: 14052
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>

using namespace std;

int main() {

	int N,X;

	cin >> N >> X;

	vector<int> L(N);

	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}

	int D = 0;

	for (int i = 0; i < N+1; i++) {

		if (D > X) {
			cout << i << endl;

			break;
		}
		if (i == N) {
			cout << i+1 << endl;

			break;
		}

		D = D + L[i];
	}


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
#define pival 3.14159265359
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pqq priority_queue
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
ll power(ll x,ll y,ll p) 
{ 
    ll res=1;  
    x=x%p;
    while (y > 0) 
    { 
        if(y&1) 
            res=(res*x)%p; 
        y=y>>1;
        x=(x*x)%p;   
    } 
    return res; 
}
ll arr[3001];
ll dp[3005][3005][5];
ll rec(ll i, ll j, ll t)
{
	if(dp[i][j][t] != -1)
		return dp[i][j][t];
	if(i == j)
	{
		if(t == 1)
			return -arr[i];
		else
			return arr[i];
	}
	dp[i+1][j][1-t] = rec(i+1,j,1-t);
	dp[i][j-1][1-t] = rec(i,j-1,1-t);
	if(t == 0)
		return dp[i][j][t] = max(arr[i] + dp[i+1][j][1-t], arr[j] + dp[i][j-1][1-t]); 
	else if(t == 1)
		return dp[i][j][t] = min(dp[i+1][j][1-t] - arr[i], dp[i][j-1][1-t] - arr[j]);
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll i,j,k,n;
    cin >> n;
    for(i=0;i<n;i++)
    	for(j=0;j<n;j++)
    		for(k=0;k<2;k++)
    			dp[i][j][k] = -1;
    for(i=0;i<n;i++)
    	cin >> arr[i];
    cout << rec(0,n-1,0) << endl;
	return 0;
}

Measured memory_bytes: 352768
/*Bismillahir Rahmanir Rahim
->>Code by Ashraful Islam Paran
->>CUET,CSE
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define f(a,b,x) for(int a=b;a<x;a++)
#define pb push_back
#define endl "\n"
#define MX 200000
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define vi vector<int>

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

    int x,y;
    cin>>x>>y;
    if(y>=2*x&&y<=4*x&&y%2==0)
        yes;
    else
        no;

    return 0;
}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int w, h;
		while (((w = s.nextInt()) != 0 && ((h = s.nextInt()) != 0))) {
			int[][] t = new int[h+1][w+2];
			int[][] d = new int[h+1][w+2];
			for (int y = 0; y <= h; y++)
				for (int x = 0; x <= w+1; x++) {
					if (1 <= x && x <= w && 1 <= y && y <= h) t[y][x] = s.nextInt();
					else t[y][x] = -1;
					d[y][x] = 0;
				}
			
			for (int x = 1; x <= w; x++) 
				if (t[1][x] == 0) d[1][x] = 1;

			for (int y = 2; y <= h; y++) 
				for (int x = 1; x <= w; x++) {
					if (t[y][x] == 0) {
						if (t[y-1][x-1] == 0) d[y][x] += d[y-1][x-1];
						if (t[y-1][x+1] == 0) d[y][x] += d[y-1][x+1];
					}
					if (t[y][x] != 1) {
						if (t[y-1][x] == 0) d[y][x] += d[y-1][x];
						if (t[y-2][x] == 2) d[y][x] += d[y-2][x];
					}
				}

			int sum = 0;
			for (int x = 1; x <= w; x++) sum += d[h][x];
			for (int x = 1; x <= w; x++) 
				if (t[h-1][x] == 2) sum += d[h-1][x];
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 1000000009
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  ll k;
  cin >> k;
  ll num = 1;
  ll first = 0;
  ll count = 0;
  ll ans = 0;
  rep(i,s.size()-1){
    if(s[i] == s[i + 1]){
      num++;
    }
    else{
      if(count == 0){
        first = num;
      }
      ans += num/2;
      count++;
      num = 1;
    }
  }
  ans += num/2;
  if(count == 0){
    cout << num*k/2 << endl;
  }
  else if(s[0] != s[s.size()-1]){
    cout << ans*k << endl;
  }
  else{
    //cout << first << num << endl;
    ll dis = (k-1)*((first+num)/2 - first/2 - num/2);
    cout << ans*k + dis << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
 int main()
 {
          int a,b,c,d,x,y;
          scanf("%d%d%d%d",&a,&b,&c,&d);
          x=(a+d-1)/d;
          y=(c+b-1)/b;
          if(x>=y)
                    printf("Yes\n");
          else
                    printf("No\n");
 return 0;
 }


Measured memory_bytes: 1652
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ll dp[107][100007];
ll sum[107][100007];
ll A[207];

int main(){
  ll N,K;
  cin >> N >> K;
  rep(i,N){
    cin >> A[i+1];
  }
  rep(i,N+1){
    dp[i][1]=1;
    sum[i][1]=1;
  }
  Rep(i,1,K+2){
    sum[0][i]=1;
  }
  Rep(i,1,N+1){
    Rep(j,2,K+2){
      dp[i][j]=sum[i-1][j]-sum[i-1][max(0LL,j-A[i]-1)];
      dp[i][j]=(dp[i][j]+MOD)%MOD;
      sum[i][j]=sum[i][j-1]+dp[i][j];
      sum[i][j]%=MOD;
    }
  }
  cout << dp[N][K+1] << endl;
}

Measured memory_bytes: 162048
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

s = ins()


def solve():
    ans = 9 * (len(s) - 1)
    x = [int(d) for d in s]
    sx = sum(x)
    ans = max(ans, sx)
    ans = max(ans, (x[0] - 1) + 9 * (len(s) - 1))
    return ans


print(solve())


Measured memory_bytes: 9188
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
S = [input() for _ in range(n)]

ans = ""
for c in ascii_lowercase:
    mi = INF
    for s in S:
        mi = min(mi, s.count(c))
    ans += c*mi
print(ans)


Measured memory_bytes: 10484