akhauriyash/Code-Regression huggingface dataset:
from math import sqrt
from collections import Counter

# 半開区間[lower, upper)の素数のリストを作成する
def make_prime_list(lower:int, upper:int) -> list:
    
    # 変数のバリデーション
    if lower < 0:
        raise ValueError("lowerは0以上でなければいけません。(lower:{})".format(lower))

    elif upper <= lower:
        raise ValueError("upperはlowerより大きい数でなければいけません。\
                         (lower:{}, upper:{})".format(lower,upper))
    
    # 素数リストの初期化    
    isPrime = [True]*upper
    primeList = []
    
    # 区間内の数字が0,1のみならここで終了
    if upper <= 2:
        return primeList
    
    # 区間内の数字に2以上のものがあるとき
    isPrime[0] = False
    isPrime[1] = False
    
    # エラトステネスの篩の処理
    for n in range(2,int(sqrt(upper))+2):
        if isPrime[n]:
            res=2*n
            while res<upper:
                isPrime[res] = False
                res += n
    
    # 区間内の素数を抽出
    for n in range(lower,upper):
        if isPrime[n]:
            primeList.append(n)
        
    return primeList


# numを素因数分解する
def factoring(num: int, prime_list: list) -> dict:
    
    # バリデーション
    if num < 2:
        raise ValueError("numは2以上でなければいけません。(num:{})".format(num))
    
    
    # numまでの素数リストを作る
    prime_set = set(prime_list)
    
    # {素数: 含まれる数}の辞書を作る
    cnt = Counter()
    res = num
    i = 0
    
    # resが素数になるまでdicに素因数を詰め続ける
    while not res in prime_set:
        if res % prime_list[i] == 0:
            cnt[prime_list[i]] += 1
            res //= prime_list[i]
        
        else:
            i += 1
            if i >= len(prime_list):
                break
            
    cnt[res] += 1
    
    return cnt


n = int(input())
prime_list = make_prime_list(0, n+1)
MOD = 10**9 + 7

cnt = Counter()
ans = 1
if n == 1:
    print(1)
    
else:
    # 素因数辞書作る
    for i in range(2,n+1):
        cnt += factoring(i, prime_list)

    # 掛け算する
    for k, v in cnt.items():
        ans = ans * (v+1) % MOD
        
    print(ans % MOD)

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b-1);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  vector<ll>a(n),b(n);
  rep(i,n){
    cin>>a[i];
  }
  rep(i,n)cin>>b[i];
  ll cnt=0;
  rep(i,n){
    cnt+=(max(0ll,b[i]-a[i])+1)/2;
    a[i]+=(max(0ll,b[i]-a[i])+1)/2*2;
  }
  rep(i,n){
    //cout<<b[i]<<" "<<a[i]<<endl;
    cnt-=a[i]-b[i];
  }
  if(cnt>=0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
     //https://www.codechef.com/viewsolution/28454497
    // https://medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define int long long
vector < ll> primes;
 int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n;
bool isvalid(int x,int y){
  return (x>=0 and x<n and y>=0 and y<n);
}
void Sieve(ll n) 
{ 
    bool prime[n+1];
	for(ll i=0;i<n+1;++i)
		prime[i]=true;
    for (ll p=2;p*p<=n;++p) 
    {
        if (prime[p] == true) 
        {  
            for (ll i=2*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    }  
    for(ll p=2; p<=n; p++) 
       if (prime[p]) 
		primes.push_back(p);  
}
 const int N = 5e5 + 5;
 	int connected;
	int par[N], sz[N];
 
struct DSU
{

	void init(int n) 
	{
		for(int i=1;i<=n;i++)
		{
			par[i]=i;
			sz[i]=1;
		}
		connected=n;
	}
 
	int getPar(int k)
	{
		while(k!=par[k])
		{
			par[k]=par[par[k]];
			k=par[k];
		}
		return k;
	}
 
	int getSize(int k)
	{
		return sz[getPar(k)];
	}
 
	void unite(int u, int v)
	{
		int par1=getPar(u), par2=getPar(v);
 
		if(par1==par2)
			return;
 
		connected--;
 
		if(sz[par1]>sz[par2])
			swap(par1, par2);
 
		sz[par2]+=sz[par1];
		sz[par1]=0;
		par[par1]=par[par2];
	}
};
 
 

DSU dsu;
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
        return gcd(b % a, a); 
} 
ll powermod(ll x, ll y){
    if(y==0)
    return 1;
        
    if(y%2==0)
    return (powermod(x,y/2)*powermod(x,y/2))%mod;
    else
    return (((powermod(x,y/2)*powermod(x,y/2))%mod)*x)%mod;
}
// vector<vector<int>>dp(3500,vector<int>(3500));

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

    int n;
    cin>>n;
    set<int>s;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    if(s.size()==n)
    {
        cout<<"YES";
    }
    else cout<<"NO";
    
    
    
}

Measured memory_bytes: 9600
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
for i in range(10**N):
    a = str(i)
    if len(a) == N and all(str(a[s-1]) == str(c) for s,c in sc):
        print(i)
        exit()
print(-1)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main()
{
	int x;
	cin>>x;
	if(x>=400&&x<=599)	
		cout<<"8"<<endl;
	else if(x>=600&&x<=799)	
		cout<<"7"<<endl;
	else if(x>=800&&x<=999)	
		cout<<"6"<<endl;
	else if(x>=1000&&x<=1199)	
		cout<<"5"<<endl;
	else if(x>=1200&&x<=1399)	
		cout<<"4"<<endl;
	else if(x>=1400&&x<=1599)	
		cout<<"3"<<endl;
	else if(x>=1600&&x<=1799)	
		cout<<"2"<<endl;
	else if(x>=1800&&x<=1999)	
		cout<<"1"<<endl;	
	return 0;
}

Measured memory_bytes: 3604
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    x=list(map(int,readline().split()))

    res=float("inf")
    for i in range(n):
        j=i+k-1
        if j>=n: break
        if x[i]*x[j]<0:
            res=min(res,-x[i]+x[j]+min(-x[i],x[j]))
        elif x[j]<=0:
            res=min(res,-x[i])
        elif x[i]>=0:
            res=min(res,x[j])

    print(res)

if __name__=="__main__":
    main()

Measured memory_bytes: 15020
import sys
N, M = map(int, input().split())

G = {k: [] for k in range(N)}
for _ in range(M):
    X, Y, Z = map(int, input().split())
    # 無向グラフ
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)

visited = [False]*N

sys.setrecursionlimit(1000000)


def dfs(ci):
    for ni in G[ci]:
        if visited[ni] is True:
            continue
        visited[ni] = True
        dfs(ni)


ans = 0
for i in range(N):
    if visited[i] is False:
        ans += 1
        visited[i] = True
        dfs(i)
print(ans)


Measured memory_bytes: 118708
#include<stdio.h>
int main(){
  int i,j,count=0,n1,n2;
  scanf("%d",&n1);
  int S[n1];
  for(i=0;i<n1;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&n2);
  int T[n2];
  for(i=0;i<n2;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<n2;i++){
    for(j=0;j<n1;j++){
      if(S[j]==T[i]){
	count++;
	break;
      }
    }
  }
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 2104
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

typedef long long ll;

using namespace std;

int solve(int n,int k){
    int a[100000];
    ll sum=0,ans=0;
    
    
    
    for(int i=0;i<k;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    
    ans=sum;
    
    for(int i=k;i<n;i++){
        scanf("%d",&a[i]);
        sum+=a[i]-a[i-k];
        ans=max(ans,sum);
    }
    
    printf("%lld\n",ans);
    
    return 0;
}

int main(){
    int n,k;
    
    while(1){
        scanf("%d%d",&n,&k);
        if(n+k==0)
            break;
        solve(n,k);
    }
    
    return 0;
}

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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)


int main()
{
    int a,b;
    cin>>a>>b;
    cout<<max(a-2*b,0);

}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <iomanip>

#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define SQ(i) ((i) * (i))
using namespace std;

int main(){
  double x1, y1, x2, y2, x3, y3;
  double a1, b1, c1, a2, b2, c2, x, y, a, b, c, cos_a, sin_a, r;
  int n;
  scanf("%d", &n);
  while(n--){
    scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);
    a1 = 2*(x2-x1);
    b1 = 2*(y2-y1);
    c1 = x1*x1 - x2*x2 + y1*y1 - y2*y2;
         
    a2 = 2*(x3-x1);
    b2 = 2*(y3-y1);
    c2 = x1*x1 - x3*x3 + y1*y1 - y3*y3;
    x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
    y = (c1 * a2 - c2 * a1) / (a1 * b2 - a2 * b1);

    r = SQ(x3-x) + SQ(y3 - y);
    r = sqrt(r);
    printf("%.3f %.3f %.3f\n",x, y, r);
  }
  return 0;
}

Measured memory_bytes: 1248
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
long long getDigit(long long n);      // 数字の桁数を取得する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      ((a)/GCD((a),(b))*(b))
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

typedef long long ll;
typedef unsigned long long ull;

// code
// ------------------------------------------------
int main() {

  ll n,m;
  cin >> n >> m;

  vector<pair<ll,ll>> drink(n);
  rep(i,n)
  {
    cin >> drink[i].first >> drink[i].second;
  }

  auto comp = [](auto a,auto b){
    return a.first < b.first;
  };

  sort(all(drink),comp);

  ll num = 0;
  ll val = 0;
  
  rep(i,n)
  {
    if(num + drink[i].second > m)
    {
      ll diff = m - num;
      val += diff * drink[i].first;
      num = m;
      break;
    }
    else
    {
      num += drink[i].second; 
      val += drink[i].first * drink[i].second;
    }
  }

  cout << val << endl;

  return 0;
}
// funcの実体
// ------------------------------------------------
ll getDigit(ll n)
{
  int i = 1;
  while(1)
  {
    n = n / 10;
    if(n == 0)
      break;
    i++;
  }
  return i;
}
ll CalcSumOfDigit(ll n)
{
  ll s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define sz(arr) (int)(arr).size()
#define rng(arr) arr.begin(), arr.end()
#define show(x) cout << #x << " = " << x << endl;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
typedef long long int ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

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

void Main() {
  Cin(int, n, k, q);
  vector<int> v(n, k);
  rep(i, q) {
    Cin(int, a);
    v[a - 1]++;
  }
  rep(i, n) cout << (v[i] - q > 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1024
S = input()

odd_number = []
even_number = []

for i in range(len(S)):
    if i % 2 == 0:
        odd_number.append(S[i])
    else:
        even_number.append(S[i])

correct = 0
        
for j in range(len(odd_number)):
    if odd_number[j] != "L":
        correct += 1

for k in range(len(even_number)):
    if even_number[k] != "R":
        correct += 1
    
if correct == len(S):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
// xx, yy, zzにそれぞれ座圧する元の配列を突っ込むとx, y, zが座圧された配列で返ってくる
// zip[座圧前] = 座圧後、unzip[座圧後] = 座圧前
VL xx, x, unzip(100010);
unordered_map<int, int> zip;
void compress() {
  x = xx;
  sort(ALL(xx));
  xx.erase(unique(ALL(xx)), xx.end());
  REP(i, xx.size()) {zip[xx[i]] = i; unzip[i] = xx[i];}
  REP(i, x.size()) x[i] = zip[x[i]];
}

int a[200010], cnt[200010];
signed main(void)
{
  int n, x;
  cin >> n >> x;
  REP(i, n) {
    cin >> a[i];
    cnt[a[i]-1]++;
  }

  int num = 0;
  REP(i, n) if(cnt[i]) num++;

  sort(cnt, cnt+n);
  int idx = 0;
  while(cnt[idx] == 0) idx++;
  int res = 0;
  // cout << num - x << endl;
  REP(i, num-x) res += cnt[idx++];
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

// dist[v] に頂点 s から頂点 v への距離を入れる関数
void dijkstra(int s, Graph &G, vector<ll> &dist){
  fill(all(dist), INF);
  dist[s] = 0;

  priority_queue<P, vector<P>, greater<P>> pq;//距離が小さい順に取り出す
  pq.push(P(0,s)); // 頂点 s からスタート

  while (!pq.empty()) {
    P p = pq.top(); pq.pop();
    int v = p.second;
    if(dist[v] < p.first) continue;// 既に v に辿り着く短い経路有ならスルー (これはただの高速化)

    for(auto e : G[v]){// v から行ける頂点 nv 達を走査
      int nv = e.to;
      ll w = e.weight;
      if(dist[nv] > dist[v] + w){
        dist[nv] = dist[v] + w;
        pq.push(P(dist[nv], nv));
      }
    }
  }
}

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};


const int MAX = 510000;
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;
    }
}

int main(){
  int H,W; cin >> H >> W;
  vector<string> a(H);
  rep(h,H) cin >> a[h];

  queue<pii> q;
  vvi d(H,vi(W,-1));
  rep(h,H) rep(w,W) {
    if(a[h][w] == '#'){
      q.push(mp(h,w));
      d[h][w] = 0;
    }
  }

  while(!q.empty()){
    int h = q.front().first;
    int w = q.front().second;
    q.pop();
    rep(dir,4) {
      int nh = h + dh[dir];
      int nw = w + dw[dir];
      if(nh < 0 || nh == H || nw < 0 || nw == W) continue;
      if(d[nh][nw] != -1) continue;
      d[nh][nw] = d[h][w] + 1;
      q.push(mp(nh,nw));
    }
  }
  int ans = 0;
  rep(h,H) rep(w,W) chmax(ans,d[h][w]);
  cout << ans << endl;
}

Measured memory_bytes: 13456
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

static class P
{
    static void Main()
    {
        string s = Console.ReadLine();
        int[] res = new int[s.Length];
        int i = 0;
        while (true)
        {
            int rCount = 0;
            while (s[i] == 'R')
            {
                rCount++;
                i++;
            }
            res[i - 1] += rCount / 2 + rCount % 2;
            res[i] += rCount / 2;
            int lInd = i;
            int lCount = 0;
            while (i < s.Length && s[i] == 'L')
            {
                lCount++;
                i++;
            }
            res[lInd - 1] += lCount / 2;
            res[lInd] += lCount / 2 + lCount % 2;
            if (i >= s.Length) break;
        }
        Console.WriteLine(string.Join(" ", res));
    }


    static readonly TextReader In = Console.In;
    static int NextInt
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get
        {
            int res = 0;
            int next = In.Read();
            int rev = 1;
            while (45 > next || next > 57) next = In.Read();
            if (next == 45) { next = In.Read(); rev = -1; }
            while (48 <= next && next <= 57)
            {
                res = res * 10 + next - 48;
                next = In.Read();
            }
            return res * rev;
        }
    }
}


Measured memory_bytes: 13152
#include <stdio.h>
#include <math.h>
#define N 10000
int isPrime(int);

int main() {
  int i,n,num[N],cnt=0;
  scanf("%d",&n);
  for (i = 0; i < n; i++) {
  scanf("%d",&num[i]);
  }
  for (i = 0; i < n; i++) {
    if (isPrime(num[i]) == 1) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}

int isPrime(int n){
  int i;
  if (n == 2) return 1;
  if (n%2 == 0 || n < 2) return 0;
  for (i = 3; i <= sqrt(n); i+=2) {
    if (n%i == 0) return 0;
  }
  return 1;
}

Measured memory_bytes: 632
L, X=map(int, input().split())
def h(l):
  if l==0:
    return 1
  else:
    return h(l-1)*2+3

def f(l,x):
  if l == 0:
    if x == 0:
      return 0
    else:
      return 1
  else:
    if x <= 1:
      return 0
    elif x <= h(l-1) + 1:
      return f(l-1, x-1)
    elif x == h(l-1) + 2:
      return f(l-1, h(l-1))+1
    elif x <= h(l-1) * 2 + 2:
      return f(l-1, h(l-1))+1+f(l-1, x - h(l-1) - 2 )
    else:
      return f(l-1, h(l-1)) * 2 + 1
print(f(L,X))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = (int)(n)-1; 0 <= i; i--)
#define rrep1(i, n) for (int i = (int)(n); 1 <= i; i--)

#define each(it, c) \
    for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define all(obj) (obj).begin(), (obj).end()

#define pcount __builtin_popcount
#define SZ(x) ((int)(x).size())
#define LEN(x) ((int)(x).length())

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

#define endl "\n"

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;
}

typedef long long lint;

using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    char a;
    cin >> a;
    cout << ('Z' < a ? "a" : "A") << endl;
}

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

int main() {
  int N, M, A;
  cin >> N >> M;
  for(int i=0; i<M; i++) {
    cin >> A;
    N-=A;
  } 
  
  cout << (N>=0 ? N : -1) << endl;
  return 0;
}

Measured memory_bytes: 3636
package main
import "fmt"

func main(){
	var A,B,C int
	fmt.Scan(&A,&B,&C)
	if A >= B && A >= C{
		fmt.Println(10*A + B + C)
	}else if B >= A && B >= C{
		fmt.Println(10*B + A + C)
	}else{
		fmt.Println(10*C + A + B)
	}

}


Measured memory_bytes: 512
import numpy as np

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

ans = [0 for i in range(n)]

arr.reverse()

for i in range(n):
    base = n-i
    sup = n//base
    now = 0
    for j in range(1,sup+1):
        now += ans[base*j-1]
    if now%2 == arr[i]%2:
        ans[base-1]=0
    else:
        ans[base-1]=1



m = sum(ans)
last = [0 for i in range(m)]
index = 0
for i in range(n):
    if ans[i] == 1:
        last[index] = i+1
        index += 1
print(m)
for i in range(m-1):
    print(last[i],end=" ")
if (m > 0):
    print(last[-1])


Measured memory_bytes: 21548
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); i++)
#define rrep(i, to) for (int i = (to) - 1; i >= 0; i--)
#define repf(i, from, to) for (int i = (from); i < (to); i++)
#define all(v) v.begin(), v.end()
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

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

  int left = n;
  int sum = 0;
  while(left > 0) {
    sum += left % 10;
    left /= 10;
  }

  if(n % sum == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3608
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,readline().split())
*a, = map(int,readline().split())
*b, = map(int,readline().split())
b = b[::-1]

same = [i for i in range(n) if a[i] == b[i]]
if same:
    v = a[same[0]] # b を逆順にしたので、重なる値は一種類しかない。これを v とおく。
    r = same[0]
    s = same[-1]+1
    notv = [i for i in range(n) if a[i]!=v and b[i]!=v] # どっちもvとかぶらない index
    if len(same) > len(notv):
        print("No")
        exit()
    
    for i,j in zip(same,notv):
        b[i],b[j] = b[j],b[i]

print("Yes")
print(*b)

Measured memory_bytes: 41480
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)
 
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.141592653589793238
#define dcout cout<<fixed<<setprecision(50)
 
const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;
 
// typedef long long ll;
#define int long long
#define double long double
 
template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
 
typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

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

  int N; cin >> N;
  int ans = VERYBIG;
  for(int i = 1; i <= 50000; i++){
    int money = floor((double)i * 1.08);
    if(N == money) ans = i;
  }
  if(ans == VERYBIG) cout << ":(" << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<unordered_map>
#include<functional>
#include<set>
#include<numeric>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define SUM(a) accumulate(all(a),0LL)
#define pb push_back
#define endl '\n'
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;

ll n = 0, m = 0, ans = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok = true, flag = false;
ll dx[5] = { 1,-1,0,0,0 }, dy[5] = { 0,0,1,-1,0 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 222222


ll a[MAX];

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


	cin >> n;
	vll b;
	MAP mp;
	rep(i, n) {
		cin >> a[i];
		b.pb(a[i]);
	}
	sort(all(b));
	rep(i, n) mp[b[i]] = i % 2;
	for (ll i = 0; i < n; i += 2) {
		if (mp[a[i]]) ans++;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 8052
import sys
input = sys.stdin.readline
n,l = map(int,input().split())
if l >= 1:
  print((l+l+n)*(n-1)//2)
elif l+n<=1:
  print((l+l+n-2)*(n-1)//2)
else:
  print((l+l+n-1)*n//2)

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

int arr[1001];

int main() {
	int n, k, sum = 0;
  cin >> n >> k;
  for(int i = 0;i < n;i += 1){
  	cin >> arr[i];
  }
  sort(arr, arr + n);
  for(int i = 0;i < k;i += 1){
  	sum += arr[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
 
int main() {
	int n;
	cin >> n;
	vector <int> a(n+1);
	int ans =0;
	for (int i = 1; i<=n; i++) {
		cin >> a[i];
		if (i %2 ==1 && a[i] %2 ==1) {
			ans++;
		}
	}
	cout << ans << endl;
}

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

typedef long long ll;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)

ll mod=1e9+7;

using namespace std;


ll inputValue(){
	ll a;
	cin >> a;
	return a;
};

void inputArray(int * p, ll a){
	rep(i, a){
		cin >> p[i];
	}
};

template<typename T>
void inputVector(vector<T>& p, ll a){
	rep(i, a){
		T input;
		cin >> input;
		p.emplace_back(input);
	}
}


template <typename T>
void output(T a) {
	cout << a << "\n";
}


ll gcd(ll a,ll b)
{
	if (a%b ==0)
		return b;
	else
		return gcd(b,a%b);
}

int main(int argc, const char * argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll a,b,c,d;
	
	cin >>a>>b>>c>>d;

	ll e,f,g,h,i,j;
	ll lcm =c*d/gcd(c,d);
	a--;	
	e = a/c;
	f = a/d;
	g = a/lcm;

	h = b/c;
	i = b/d;
	j = b/lcm;
	
	cout << b-(h+i-j)-(a-(e+f-g)) << endl;
	//cout << gcd(c,d) << endl;
}


Measured memory_bytes: 256
N=int(input())
a,w,t,r=0,0,0,0
for i in range(N):
    S=input()
    if S=='AC':
        a+=1
    elif S=='WA':
        w+=1
    elif S=='TLE':
        t+=1
    elif S=='RE':
        r+=1
print('AC x '+str(a))
print('WA x '+str(w))
print('TLE x '+str(t))
print('RE x '+str(r))


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

int main() {

    int A,B;
    cin >> A >> B;

    int count, s;
    count = 0;
    s = 1;

    while ( s < B) {
        s --;
        s += A;
        count++;
    }

    cout << count << endl;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll rec(int n,ll x){
    if(n==0) return 1;
    ll len=(1LL<<(n+1))-3;
    ll num=(1LL<<n)-1;
    if(x==1) return 0;
    else if(x<=len+1) return rec(n-1,x-1);
    else if(x==len+2) return num+1;
    else if(x<=(len+1)*2) return num+1+rec(n-1,x-len-2);
    else return num*2+1;
}

int main() {
    int n;
    ll x;
    cin>>n>>x;
    cout<<rec(n,x)<<endl;
}




Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    ll n;
    cin >> n;
    vector<ll> p(n);
    Rep (i, n) cin >> p[i];

    ll ans = 0;
    for (ll i = 1; i < n-1; i++) {
        if (p[i-1] < p[i] && p[i] < p[i+1] || p[i-1] > p[i] && p[i] > p[i+1]) {
            ans++;
            // cout << i << "\n";
        }
    }

    cout << ans << "\n";
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n, c; std::cin >> n >> c;
  vvi conv(c, vi(c));
  rep(i, c) rep(j, c) {
    std::cin >> conv[i][j];
  }
  vvi grid(n, vi(n));
  rep(i, n) rep(j, n) {
    std::cin >> grid[i][j];
  }

  vector<map<int, int>> cnt(3);
  rep(i, n) rep(j, n) {
    cnt[(i+j)%3][grid[i][j]]++;
  }
  ll ans = 1e18;
  rep(x, c) rep(y, c) rep(z, c) if (x != y && x != z && y != z) {
    ll tmp = 0;
    vi to = {x, y , z};
    rep(i, 3) {
      for (auto &p : cnt[i])
        tmp += conv[p.fi-1][to[i]] * p.se;
    }
    chmin(ans, tmp);
  }
  std::cout << ans << "\n";
}


Measured memory_bytes: 1280
s = int(input())
mod = 10**9+7

dp = [0] * (s+1)
dp[0] = 1
x = 0
for i in range(1,s+1):
  if i - 3 >= 0:
    x += dp[i-3]
    x %= mod
  dp[i] = x
print(dp[s])

Measured memory_bytes: 9076
#include"bits/stdc++.h"
using namespace std;
 
#define MAX 502
#define ull unsigned long long int 
int n;
int ty_r[MAX];
ull val_r[MAX];
int ty_c[MAX];
ull val_c[MAX];
bool tmp[MAX][MAX];
int emp[MAX];
ull ans[MAX][MAX];
void transpose(){
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++)swap(tmp[i][j],tmp[j][i]);
		swap(val_r[i],val_c[i]);
		swap(ty_r[i],ty_c[i]);
	}
}
void fi(long long int pos){
	memset(emp, 0, sizeof(emp));
	for (int j = 0; j < n; j++) {
		if (ty_c[j] == false) {
			emp[j] = n - 1;
			for (int k = 0; k < n; k++) emp[j]-=tmp[k][j];
		}
	}
	for (int i = 0; i < n; i++) {
		if (ty_r[i]) {
			if (((val_r[i]) >> pos) & 1ULL) {
				bool valid = false;
				for (int j = 0; j < n; j++) valid|=tmp[i][j];
				if (valid == false) {
					for (int j = 0; j < n; j++) {
						if (emp[j]>0) { 
							emp[j]--;
							tmp[i][j] = true;
							break;
						}
					}
				}
			}
		}
	}
}
void solve(ull pos) {
	memset(tmp, false, sizeof(tmp));
	for (int i = 0; i < n; i++) {
		if (ty_r[i]==false&&((val_r[i]) >> pos) & 1ULL) for (int j = 0; j < n; j++) tmp[i][j] = 1;
		if(ty_c[i]==false&&((val_c[i]) >> pos) & 1ULL) for (int j = 0; j < n; j++) tmp[j][i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ty_r[i] == ty_c[j]) {
				if (ty_r[i] == false) tmp[i][j] = ((val_r[i] >> pos) & 1ULL)| ((val_c[j] >> pos) & 1ULL);
				else tmp[i][j] = ((val_r[i] >> pos) & 1ULL)& ((val_c[j] >> pos) & 1ULL);
			}
		}
	}
	fi(pos);
	transpose();
	fi(pos);
	transpose();
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ans[i][j] += ((ull)(tmp[i][j]) << pos);
}
void fo(){
	puts("-1");
	exit(0);
}
void check() {
	for (int i = 0; i < n; i++) {
		ull AN = -1; ull O = 0; ull AN2 = -1; ull O2 = 0;
		for (int j = 0; j < n; j++) {
			AN &= ans[i][j];
			O |= ans[i][j];
			AN2&=ans[j][i];
			O2|=ans[j][i];
		}
		if (ty_r[i] == false&&AN != val_r[i]) fo();
		else if(ty_r[i] == true&&O!=val_r[i]) fo();
		if (ty_c[i] == false&&AN2 != val_c[i]) fo();
		else if (ty_c[i] && O2 != val_c[i]) fo();
	}
}
int main() {
		cin>>n;
		for (int i = 0; i < n; i++) scanf("%d", &ty_r[i]);
		for (int j = 0; j < n; j++) scanf("%d", &ty_c[j]);
		for (int i = 0; i < n; i++) scanf("%llu", &val_r[i]);
		for (int j = 0; j < n; j++) scanf("%llu", &val_c[j]);
		for (int i = 0; i < 64; i++) solve(i);
		check();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j)printf(" ");
				printf("%llu", ans[i][j]);
			}
			puts("");
		}
	return 0;
}

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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

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

using pii = pair<int, int>;

struct State {
    int x, y, d;
    pii val;

    bool operator < (const State& o) const { return val > o.val; }
};

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    int sx, sy, gx, gy;
    cin >> sy >> sx >> gy >> gx;
    --sx; --sy; --gx; --gy;

    vector<string> grid(H);
    for_(i,0,H) cin >> grid[i];

    vector<vector<vector<pii>>> dst(H, vector<vector<pii>>(W, vector<pii>(5, {1L << 30, -(1L << 30)})));
    dst[sy][sx][4] = pii(0, 0);

    priority_queue<State> que;
    que.push(State{sx, sy, 4, {0, 0}});

    while (!que.empty()) {
        State s = que.top(); que.pop();
        if (dst[s.y][s.x][s.d] < s.val) continue;
        
        for_(d,0,4) {
            int nx = s.x + dx[d], ny = s.y + dy[d];
            if (nx < 0 or nx >= W or ny < 0 or ny >= H) continue;
            if (grid[ny][nx] == '@') continue;

            pii nval;
            if (d == s.d and s.val.second < 0) {
                nval.first = s.val.first;
                nval.second = s.val.second + 1;
            }
            else {
                nval.first = s.val.first + 1;
                nval.second = -(K - 1);
            }

            if (dst[ny][nx][d] > nval) {
                dst[ny][nx][d] = nval;
                que.push(State{nx, ny, d, nval});
            }
        }
    }

    pii ans(1L << 30, -(1L << 30));
    for_(d,0,4) ans = min(ans, dst[gy][gx][d]);
    cout << (ans.first == 1L << 30 ? -1 : ans.first) << endl;
}

Measured memory_bytes: 144880
n = int(input())

b = list(map(int,input().split()))

a = [0 for _ in range(n)]
a[0] = b[0]
a[1] = b[0]
for i in range(1,n-1):
    a[i] = min(b[i],a[i])
    a[i + 1] = b[i]
    
print(sum(a))


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[100000];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; a[i]--; }
	
	int ans = 0, p = 0;
	while(true) {
		int t = a[p];
		a[p] = -1;
		p = t;
		ans++;
		if(p == 1) { break; }
		if(p == -1) { ans = -1; break; }
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

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

  string s;
  s = to_string(n);
  int ans = 0;
  rep(i, s.size()) ans += s[i] == '2';
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
from itertools import permutations

n = int(input())
per = []
for i in permutations(range(1, n+1)):
    per.append(i)

p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

a = per.index(p)
b = per.index(q)

print(abs(a-b))

Measured memory_bytes: 7924
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val s = sc.next()
    println(problem095a(s))
}

fun problem095a(s: String): Int {
    var price = 700
    if (s[0] == 'o') price += 100
    if (s[1] == 'o') price += 100
    if (s[2] == 'o') price += 100
    return price
}

Measured memory_bytes: 29600
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mpcy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef vector<int> poly;
const int MAXN = 300005;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = - 1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, a[MAXN], sum[MAXN], B, W;

inline bool check(int M) {
	int pre = 0;
	for (int i = 2; i <= n; i += 2) {
		if (sum[i - 1] - pre >= M) {
			pre = min(pre, sum[i]);
		}
	}
	return (sum[n] - pre >= M);
}

void init() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		if (i & 1) {
			B += a[i];
			sum[i] = sum[i - 1] + a[i];
		} else {
			W += a[i];
			sum[i] = sum[i - 1] - a[i];
		}
	}
}

void solve() {
	if (n % 2 == 0) {
		printf("%d %d\n", max(B, W), min(B, W));
		return;
	}
	int L = -3e8, R = -L, P;
	while (L <= R) {
		int M = (L + R) >> 1;
		if (check(M)) {
			L = (P = M) + 1;
		} else {
			R = M - 1;
		}
	}
	int A = max(B, W + P);
	printf("%d %d\n", A, B + W - A);
}

int main() {
	init();
	solve();
	return 0;
}


Measured memory_bytes: 6088
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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
#import numpy as np
#from decimal import *

SA = list(input())
SB = list(input())
SC = list(input())
S = {"a":SA, "b":SB, "c":SC}
turn = "a"
while 1:
	if len(S[turn]) == 0:
		break
	turn = S[turn].pop(0)

print(turn.upper())

Measured memory_bytes: 5148
import numpy as np
import sys

s = input()

tempNum = int(s)

np1_array = np.array([int(s)])

count = 1
while(True):

    checkNum = tempNum % 2

    # 割り切れたとき
    if checkNum == 0:
        tempNum = tempNum / 2
        np1_array = np.append(np1_array,tempNum)
    else:
        tempNum = 3 * tempNum + 1
        np1_array = np.append(np1_array,tempNum)

    count = count + 1

    checkNum2 = np.count_nonzero(np1_array == tempNum)
    if checkNum2 == 2:
        print(count)
        sys.exit()
    # if count == 20:
    #     print("強制終了です")
    #     sys.exit()


Measured memory_bytes: 12428
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double EPS = 1e-10;
const int INF = 2147483647;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int main()
{
	int n, k;
	int ans = 1;

	cin >> n >> k;

	for (int i = 0;i < n;i++) {
		ans = std::min(2 * ans, ans + k);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
n, t = [int(item) for item in input().split()]
ts = [int(item) for item in input().split()]

total = 0
for i in range(n):
    if i == 0:
        total += ts[i]
        continue
    total += min(ts[i] - ts[i-1], t)
total += t
print(total)

Measured memory_bytes: 25200
#include <stdio.h>

int main() {
    char s[5], t[5];
    int x=0;
    scanf("%[CSR] %[CSR]", s, t);
    for (int i=0; i<3; ++i) {
        if (s[i] == t[i]) ++x;
    }
    printf("%d\n", x);
    return 0;
}


Measured memory_bytes: 128
/*		Author : Kaustubh Gangwar
		||S||A||M||R||A||T||
*/
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ld long double
#define pb push_back
#define gcd __gcd
#define vii vector<int>
#define vll vector<long long>
#define all(x) x.begin(),x.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define fe(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
typedef long long  ll;
typedef pair<int,int> pii;

ll bpow(ll a, ll b) {
	a=a; ll res = 1;
    while(b){
        if (b & 1)
        res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int32_t main()
{	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll test=1;
	//cin>>test;
	while(test--)
	{
		ll a,b;
		cin>>a>>b;
		cout<<(a*b)/gcd(a,b);
		
	}
return 0;
}


Measured memory_bytes: 3640
w,h,n=[int(i) for i in input().split()]
#二次元配列の作成
list_2d=[[0]*w for i in range(h)]


def nurie(x,y,a):
   if a==1:
       for i in range(h):
           for j in range(x):
               list_2d[i][j]=1
   elif a==2:
       for i in range(h):
           for j in range(x,w):
               list_2d[i][j]=1
               

   elif a==3:
       for i in range(y):
           for j in range(w):
               list_2d[i][j]=1
              
   else:
       for i in range(y,h):
           for j in range(w):
               list_2d[i][j]=1
   return list_2d
               
for i in range(n):
   x,y,a=[int(i) for i in input().split()]
   nurie(x,y,a)
   
sum=0
for i in range(h):
   sum+=list_2d[i].count(0)
   
print(sum)

Measured memory_bytes: 9200