akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: u32 = read();
    let r: u32 = read();
    
    if n >= 10 {
        println!("{}", r);
    } else {
        println!("{}", r + 100 * (10 - n));
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int m;
  cin >> m;
  cout << 48 - m << endl;
}


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

int main() {
  int N; cin >> N;
  vector<vector<int>> A(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) cin >> A.at(i).at(j);
  }
  long long ans = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i+1; j < N; j++) {
      bool ok = true;
      bool need = true;
      for (int k = 0; k < N; k++) {
        if (k == i || k == j) continue;
        if (A.at(i).at(j) > A.at(i).at(k) + A.at(k).at(j)) ok = false;
        if (A.at(i).at(j) == A.at(i).at(k) + A.at(k).at(j)) need = false;
      }
      if (!ok) { cout << -1 << endl; return 0; }
      if (need) ans += A.at(i).at(j);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3996
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def search(ary, target):
    left = 0
    right = len(ary)
    while (left < right):
        idx = (left+right)//2
        if ary[idx] == target:
            return True
        if ary[idx] < target:
            left = idx + 1
        elif ary[idx] > target:
            right = idx
        else:
            return False
    return False

result = 0;
for i in t:
    if search(s, i):
        result += 1
print(result)



Measured memory_bytes: 16712
N=int(input())
A=input().split()
count_2=0
count_3_5=0
for i in range(N):
    if int(A[i])%2==0:
        count_2+=1
        if int(A[i])%3==0 or int(A[i])%5==0:
            count_3_5+=1
if count_2==count_3_5:
    print("APPROVED")
else:
    print("DENIED")


Measured memory_bytes: 3064
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return "Not stable"
    return "Stable"
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print(isStable(A))
print("\n".join(f"{a} {b}" for a, b, c in A))



Measured memory_bytes: 26996
#include <iostream>
#include <string>
#include <stdio.h>
#define INF 900000000
#define int long long
using namespace std;

//N^x


signed main(){
  int Q[4]; // 値段
  int Qperl[4]; // 8 (/4L)あたりの値段
  int L[4]={1,2,4,8}; //なん(/4L)分か
  int N;  //なん(/4L)分必要か
  int now=0,money=0; //今の (/4L)量とお金

  for(int i=0;i<4;i++){
    cin >> Q[i];
    Qperl[i]=Q[i]*(8/L[i]);
  }
  cin >> N;
  N*=4;

  //minを洗い出す
  for(int i=0;i<4;i++){
    int min=0;
    for(int i=0;i<4;i++){
      if(Qperl[min]>Qperl[i]) min=i;
    }
    while(now<=N){
      now+=L[min];
      money+=Q[min];
    }
    now-=L[min];
    money-=Q[min];
    Qperl[min]=INF;
  }
  cout << money;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define fore(i, init, n) for(int i = init; i <= n; i++)
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fs first
#define sc second
#define INF (1LL<<61)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MAXN = 1e5+5;
int n, k, h[MAXN], dp[MAXN];

int main() {
    cin >> n >> k;
    
    fore(i,1,n) cin >> h[i];

    dp[1] = 0;
    for(int i = 2; i <= n; i++) dp[i] = 1e9;
    
    for(int i = 2; i <= n; i++) {
        for(int j = k; j >= 1; j--) {
            if (i-j >= 1) {
                dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
            } 
        }

    }

    cout << dp[n];
    
}


Measured memory_bytes: 1024
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << endl;
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << "";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define wh while
#define ve vector
#define mp make_pair
#define tp tuple
#define mt make_tuple
#define pb push_back
#define pof pop_front
#define pob pop_back
#define pf push_front
#define fr front
#define ft first
#define sc second
#define tos to_string
#define len length
#define rt return
#define br break
#define con continue
#define lcm(n, m) (n * m / __gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m) - 1;i>=(int)(n);i--)
#define rev(i, m) revi(i, m, 0)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) n.begin(), n.end()
#define allr(n) n.rbegin(), n.rend()
#define sp(n) cout << fixed << setprecision(n)
#define pi 3.14159265358979323846
#define inf 1000000007
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

ve<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

int main() {
  ld a, b;
  ci(a, b);
  sp(0);
  co((floor)(a * b));
}


Measured memory_bytes: 3836
/* ~/lib/template.cを引用 */
#include<stdio.h>
#include<stdlib.h>
// #inclide<math.h>

int main(int argc, char *argv[]){

  int S, h, m, s;

  scanf("%d", &S);

  if(S < 0 || 86400 <= S) exit(0);

  h = S/3600;
  m = (S - h*3600) / 60;
  s = S - (h*3600 + m*60);

  printf("%d:%d:%d\n",h, m, s );


  return 0;
}



Measured memory_bytes: 2108
#include <iostream>
#include <deque>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    deque<int> dq;
    for(int i = 1; i < n+1; ++i){
        int a; cin >> a;
        if(n%2 == i%2) dq.push_front(a);
        else dq.push_back(a);
    }
    for(int x : dq){
        cout << x << endl;
    }
    return 0;
}
//Saw the editorial

Measured memory_bytes: 4452
#include <iostream>

using namespace std;

int main()
{
    int N;
    long c[5] = {};
    cin >> N;
    char **names = new char*[N];
    for(int i=0;i<N;i++){
        names[i] = new char[10];
        cin >> names[i];
        if(names[i][0]=='M') c[0]++;
        if(names[i][0]=='A') c[1]++;
        if(names[i][0]=='R') c[2]++;
        if(names[i][0]=='C') c[3]++;
        if(names[i][0]=='H') c[4]++;
    }
    long long combination = 0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<4;j++){
            for(int k=j+1;k<5;k++){
                combination += (long long)(c[i] * c[j] * c[k]);
            }
        }
    }
    printf("%lld\n", combination);
    return 0;
}


Measured memory_bytes: 4096
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
//#include <stack>
//#include <queue>

/*
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 
 

#include <math.h>


int main(){

    long long N;
    cin >> N ;
    string ans="";
    if(N==0){
        cout << 0;
    }else{

        long long  volume=0;

        long long  calc;
        if(N%2==0){
            ans = "0";
        }else{
            ans = "1";
            volume = 1;
        }
        calc = -2;
        while(volume != N){
            if((N - volume) % (calc * 2)==0){
                ans = "0" + ans;
            }else{
                volume += calc;
                ans = "1" + ans;
            }
            calc = calc * -2;
            //cout << "ans:" << ans << "calc:" << calc << " volume:" << volume << endl;
        }
        cout << ans;
    }

}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
    ll n;cin >> n;
    ll h;cin >> h;
    priority_queue <ll> a;
    priority_queue <ll> b;
    for(int i=0;i<n;i++){
        ll tmpa,tmpb;
        cin >> tmpa;cin >> tmpb;
        a.push(tmpa);
        b.push(tmpb);
    }
    ll ans = 0;
    while(h > 0){
        if((b.empty()) || a.top() > b.top()){
            ans += (h-1+a.top())/a.top();
            h = 0;
        }
        else{
            ans ++;
            h -= b.top();
            b.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  ll k, a, b;
  string ans;
  cin >> k >> a >> b;
  if(b<k){
    ans = "NG";
  }
  if(a%k==0 || (a+(k-(a%k)))<= b){
    ans = "OK";
  }else{
    ans = "NG";
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
string s;
int main() {
	cin>>s;
	s[3]='8';
	cout<<s;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<cstdio>
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
/*
inline int read(){
	int res=0; char ch=getchar_unlocked();
	while(ch<'0'||ch>'9') ch=getchar_unlocked();
	while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48),ch=getchar_unlocked();
	return res;
}
*/
#define int long long
#define mp make_pair
#define pb push_back
#define S second
#define F first
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define pii pair<int,int>
#define endl cout<<'\n';
#define LINE cout << "-----------------------\n";
using namespace std;
const int maxn = 1e6+5;
bitset<maxn> notok;
signed main(){
	IOS;
	int x , n ; cin >> x >> n;
	for(int i=1 ; i<=n ; ++i){
		int a; cin >> a;
		notok[a]=1;
	}
	if(!notok[x]){
		cout << x << '\n';
		return 0;
	}
	int l=-1e9 , r=-1e9;
	for(int i=x-1 ;  ; --i){
		if(!notok[i]) {
			l = i;
			break;
		}
	}
	for(int j=x+1 ;  ; ++j){
		if(!notok[j]){
			r = j;
			break;
		}
	}
	if(l == -1e9) cout << r << '\n';
	else if(r == -1e9) cout << l << '\n';
	else {
		if(abs(l - x) <= abs(r - x)) cout << l << '\n';
		else cout << r << '\n';
	}
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n+1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int> dist(n+1, -1), ans(n+1, 0);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : graph[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v]+1;
                q.push(u);
                ans[u] = v;
            }
        }
    }
    bool ok = true;
    for (int i = 2; i < n+1; i++) {
        if (ans[i] == 0) ok = false;
    }
    if (ok) {
        cout << "Yes" << endl;
        for (int i = 2; i < n+1; i++) cout << ans[i] << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 10168
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = int(inputs[0])
    sq = int(math.sqrt(N)) + 1
    min_s = None
    for n in range(1, sq + 1):
        if N % n == 0:
            m = N // n
            len_m = len(str(m))
            if min_s is None or min_s > len_m:
                min_s = len_m
    return min_s


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 39408
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define type 26

int constant(int day)//1~26 順番
{
  return day%type+1;
}
int get_random()//1~26 ランダム
{
  return rand()%type+1;
}
int max(int s[][type+1],int day)//その日の最大の満足度選ぶ
{
  int m,max_score=0,i;
  for(i=1;i<=type;i++)
  {
    if(s[day][i]>max_score){
      max_score=s[day][i];
      m=i;
    }
  }
  return m;
}
void cal(int select,int c[type+1],int last[type+1],int s[][type+1],int day,int sum[])
{
  int i;
  sum[day]=sum[day-1]+s[day][select];
  for(i=1;i<=type;i++){
    sum[day]-=c[i]*(day-last[i]);
  }
}
void change(int c[type+1],int last[type+1],int s[][type+1],int sum[],int schedul[],int D)
//ランダムに変更
{
  int d,t,old,total=0,i,j;
  d=rand()%D+1;
  t=rand()%type+1;
  old=schedul[d];
  schedul[d]=t;
  for(i=1;i<=type;i++) last[i]=0;
  for(i=1;i<=D;i++){
    total+=s[i][schedul[i]];
    last[schedul[i]]=i;
    for(j=1;j<=type;j++){
     total-=c[j]*(i-last[j]);
   }
  }
  if(total>sum[D]){
  //  printf("change\n");
    sum[D]=total;
  }
  else{
    schedul[d]=old;
  }
}
void cross(int c[type+1],int last[type+1],int s[][type+1],int sum[],int schedul[],int D)
{
  int a,b,old_a,old_b,flag=0,i,j,total=0;
  flag=rand()%2;
  a=rand()%D+1;
  if(flag==0){
    b=a+rand()%16+1;
    if(b>D) b=a-(rand()%16+1);
  }
  else{
    b=a-(rand()%16+1);
    if(b<1)   b=a+rand()%16+1;
  }
  old_a=schedul[a];
  old_b=schedul[b];
  schedul[a]=old_b;
  schedul[b]=old_a;
  for(i=1;i<=type;i++) last[i]=0;
  for(i=1;i<=D;i++){
    total+=s[i][schedul[i]];
    last[schedul[i]]=i;
    for(j=1;j<=type;j++){
     total-=c[j]*(i-last[j]);
   }
  }
  if(total>sum[D]){
    sum[D]=total;
  }
  else
  {
    schedul[a]=old_a;
    schedul[b]=old_b;
  }
}
int main(void)
{
  int D,c[type+1],i,j;
  clock_t start,stop;
  srand((unsigned int)time(NULL));
  scanf("%d",&D);//D=365
  int s[D+1][type+1],last[type+1],sum[D+1],schedul[D+1];
  for(i=0;i<=D;i++) sum[i]=0;
  for(i=1;i<=type;i++) last[i]=0;
  for(i=1;i<=type;i++) scanf("%d",&c[i]);
  for(i=1;i<D+1;i++){
    for(j=1;j<=type;j++) scanf("%d",&s[i][j]);
  }
  start=clock();
  for(i=1;i<D+1;i++){
    int select;
    select=constant(i);
    last[select]=i;
    schedul[i]=select;
    cal(select,c,last,s,i,sum);
    //printf("%d\n",sum[i]);
  }
  int count=0;
  stop=start;
  while((double)(stop - start) / CLOCKS_PER_SEC<1.98){
    int flag=rand()%2;
    if(flag==0) cross(c,last,s,sum,schedul,D);
    else change(c,last,s,sum,schedul,D);
    count++;
    stop=clock();
  }
/*
  printf("count:%d\n",count);
  printf("time:%f\n",(double)(stop - start) / CLOCKS_PER_SEC);
  printf("%d\n",sum[D]);
  printf("確認\n");
  int total=0;
  for(i=1;i<=type;i++) last[i]=0;
  for(i=1;i<=D;i++){
    total+=s[i][schedul[i]];
    last[schedul[i]]=i;
    for(j=1;j<=type;j++){
     total-=c[j]*(i-last[j]);
   }
  }
  printf("%d\n",total);
*/
  for(i=1;i<=D;i++) printf("%d\n",schedul[i]);
  return 0;
}


Measured memory_bytes: 1840
#include<bits/stdc++.h>
#define L long long
#define LL long long
using namespace std;
const int q=924844033;
const int M = 21, P = 924844033, G = 5;
const int MaxN = (1 << 20) + 10;
int N = 1 << 19;

inline int add(int a, int b) {
    return (a + b) % P;
}

inline int sub(int a, int b) {
    return (a - b + P) % P;
}

inline int mul(int a, int b) {
    return (LL)a * (LL)b % P;
}

inline int exp(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}

inline int inv(int x) {
    return exp(x, P - 2);
}

int eps[MaxN], ieps[MaxN], temp[5][MaxN];

inline void init() {
    int g = exp(G, (P - 1) / N), ig = inv(g);
    eps[0] = ieps[0] = 1;
    for (int i = 1; i < N; i++) eps[i] = mul(eps[i - 1], ig), ieps[i] = mul(ieps[i - 1], g);
}

inline void trans(int n, int x[], int w[]) {
    for (int i = 0, j = 0; i != n; i++) {
        if (i < j) std::swap(x[i], x[j]);
        for (int l = n >> 1; (j ^= l) < l; l >>= 1);
    }
    for (int i = 2; i <= n; i <<= 1) {
        int l = i >> 1, d = N / i;
        for (int j = 0; j != n; j += i)
            for (int k = 0; k != l; k++) {
                int t = mul(x[j + k + l], w[d * k]);
                x[j + k + l] = sub(x[j + k], t);
                x[j + k] = add(x[j + k], t);
            }
    }
}

inline void dft(int n, int x[]) {
    trans(n, x, eps);
}

inline void idft(int n, int x[]) {
    trans(n, x, ieps);
    for (int i = 0, in = inv(n); i < n; i++) x[i] = mul(x[i], in);
}

int n,x[800010],y[800010],p;
vector<int> a[200010];
inline int dfs(int i,int j)
{
	int k,l=1,u;
	for(k=0;k<a[i].size();k++)
	  if(a[i][k]!=j)
	    {
		 u=dfs(a[i][k],i);
		 l+=u;
		 x[u]++;
		 x[n-u]++;
		}
	return l;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	init();
	scanf("%d",&n);
	for(i=1;i<n;i++)
	  {
	   scanf("%d%d",&j,&k);
	   a[j].push_back(k);
	   a[k].push_back(j);
	  }
	dfs(1,0);
	y[n]=1;
	for(i=1,k=1;i<=n;i++,k=(L)k*i%q)
	  {
	   x[i]=(L)x[i]*k%q;
	   y[n-i]=exp(k,q-2);
	  }
	for(p=1;p<n;p<<=1);
	p<<=1;
	dft(p,x);
	dft(p,y);
	for(i=0;i<p;i++)
	  x[i]=(L)x[i]*y[i]%q;
	idft(p,x);
	for(i=1,j=n,k=1;i<=n;i++,j=(L)j*(n-i+1)%q*exp(i,q-2)%q,k=(L)k*i%q)
	  printf("%d\n",int(((L)j*n-(L)x[n+i]*exp(k,q-2))%q+q)%q);
	return 0;
}

Measured memory_bytes: 34816
#include<stdio.h>

int main(){
int n,a,min = 1001,max = -1;
scanf("%d",&n);
for(;n > 0;n--){
scanf("%d",&a);
if(max < a){max = a;}
if(min > a){min = a;}
}
printf("%d\n",max-min);
return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, s[N][N], ans, c[N][N], f[N];
int qpow(int a, int b, int mod) {
    int c = 1;
    while(b) {
        if(b & 1) c = 1ll * c * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return c;
}
int main() {
    scanf("%d %d", &n, &m);
    s[0][0] = 1;
    ++n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            s[i][j] = (1ll * j * s[i - 1][j] + s[i - 1][j - 1]) % m;
    c[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
    }
    --n;
    for(int i = 0; i <= n; ++i) {
        int b1 = qpow(2, n - i, m - 1), b2 = qpow(2, n - i, m);
        for(int j = 0; j <= i; ++j)
            (f[i] += 1ll * s[i + 1][j + 1] * qpow(b2, j, m) % m) %= m;
        f[i] = 1ll * f[i] * c[n][i] % m * qpow(2, b1, m) % m;
        if(i & 1) (ans -= f[i]) %= m;
        else (ans += f[i]) %= m;
    }
    printf("%d\n", (ans + m) % m);
    return 0;
}


Measured memory_bytes: 58908
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll X;
    cin >> X;

    if(X >= 30){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
using namespace std;

int main(){
  int n; cin>>n;
   string s; cin >>s;
  int k; cin >>k;

  char f=s[k-1];

  for(int i=0;i<n;i++){
    if(s[i]!=f)s[i]='*';
  }
  cout<<s<<endl;
}


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

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

//------------------------- Libraries -------------------------//

//--------------------------- Solve ---------------------------//

void solve() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    long long money = 1000, stock = 0;
    for (int i = 0; i < N-1; i++) {
        stock = 0;
        if (A[i] < A[i+1]) {
           stock = money / A[i];
            money += (A[i+1] - A[i]) * stock;
        }
    }

    cout << money << '\n';
}

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

    solve();

    return 0;
}

Measured memory_bytes: 3556
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

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

int GetDigit(unsigned long long num){
    return log10(num) + 1;
}

int main(){
    ll max = 1000000000000000001;
    int N;
    cin >> N;

    int keta1;
    int keta2;
    unsigned long long count;
    unsigned long long ai;
    vector<unsigned long long> A;
    int i;

    for(i=0;i<N;i++){
        cin >> ai;
        A.push_back(ai);
        if(ai==0){cout << 0 << endl; return 0;}
    }

    for(i=0;i<N;i++){
        ai = A[i];
        if(i==0){count=ai;continue;}
        keta1 = GetDigit(count);
        keta2 = GetDigit(ai);

        //cout << keta1 + keta2 - 2 << endl;
        if(((keta1 + keta2 - 2) == 17)){
            if(count * ai >= max){cout << "-1" << endl; return 0;}
        }
        else if((keta1 + keta2 - 2 ) == 18){
            if(count * ai != max - 1){cout << "-1" << endl; return 0;}
        }
        else if((keta1 + keta2 - 2) >= 19){cout << "-1" << endl; return 0;}
        count = count * ai;
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
    #include<cmath> 
     
    #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
    #define SUBL freopen("/home/ajinkya/Desktop/input.txt","r",stdin); freopen("/home/ajinkya/Desktop/output.txt","w",stdout); 
    #define ll long long
    #define ull unsigned long long
    #define FI(i,a,n) for(int i=a; i<=n; i++)
    #define RFI(i,n,a) for(int i=n; i>=a; i--)
    #define FLL(i,a,n) for(ll i=a; i<=n; i++)
    #define RFLL(i,n,a) for(ll i=n; i>=a; i--)
    #define vi vector<int>
    #define vll vector<ll>
    #define all(v) v.begin(),v.end()
    #define pll pair<ll,ll>
    #define pi pair<int, int>
    #define GCD(a,b) __gcd(a,b)
    #define MP make_pair
    #define PB push_back
    #define PF push_front
    #define LB lower_bound
    #define UB upper_bound
    #define debug(x) cout << x << endl
    #define MOD 1000000007
    #define INF LLONG_MAX
    #define PI 3.14159265359
    using namespace std;
     
     
    int main()
    {
        fastio 
        // SUBL
      	int a;
      	string s;
      	cin >> a >> s;
      	if(a>=3200) cout << s ;
      	else cout << "red";
        return 0;
    }         	

Measured memory_bytes: 256
#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 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; }

// ---- ----

const int M = 200000;
int n, a[M], b[M];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	inc(i, n) { cin >> b[i]; }
	
	int ans = 0;
	dec(k, 28 + 1) {
		inc(i, n) {
			a[i] &= ((2 << k) - 1);
			b[i] &= ((2 << k) - 1);
		}
		sort(a, a + n);
		sort(b, b + n, greater<>());
		
		int c = 0, p1 = 0, p2 = 0, p3 = 0;
		inc(i, n) {
			while(p1 < n && a[i] + b[p1] >= (1 << k)) { p1++; }
			while(p2 < n && a[i] + b[p2] >= (2 << k)) { p2++; }
			while(p3 < n && a[i] + b[p3] >= (3 << k)) { p3++; }
			c ^= (p1 - p2 + p3) & 1;
		}
		ans |= c << k;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
long long mypow(long long x, int n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
int main(){
	int h, w, k;
	cin >> h >> w >> k;
	vector<vector<int>>  c(h, vector<int>(w));
	for(int i=0; i<h; ++i){
		for(int j=0; j<w; ++j){
			char tmp;
			cin >> tmp;
			c[i][j]=(tmp=='#'? 1 : 0);
		}
	}
	
	int ans=0;
	for(int i=0; i<mypow(2,h); ++i){
		for(int j=0; j<mypow(2,w); ++j){
			int tmp=0;
			for(int ii=0; ii<h; ++ii){
				if((i>>ii)&1) continue;
				for(int jj=0; jj<w; ++jj){
					if((j>>jj)&1) continue;
					tmp += c[ii][jj];
				}
			}
			if(tmp==k) ++ans;
		}
	}
	cout << ans << endl;
}

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

typedef long long ll;
typedef unsigned long long ull;

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

  if ((a >= 1 && a <= 9) && (b >=1 && b <=9)) {
    cout << a * b << endl;
  } else {
    cout << "-1" << endl;
  }
  
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll a,b,c;

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

  cin>>a>>b>>c;
  cout<<max(0LL,c-(a-b))<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a[500001],b[500001];
inline int f(int x)
{
	for(int i=0;i<n;i++)b[i]=(a[i]>=x);
	bool f=1;
	for(int i=1;i<n;i++)
		if(b[i]==b[i-1]){f=0;break;}
	if(f)return b[0];
	int best=n,ans=0,m=n/2;
	for(int i=0;i<n;)
	{
		int j=i;
		while(j+1<n&&b[j+1]==b[j])j++;
		if(i==j){i++;continue;}
		int val=(i<=m&&m<=j?0:(i>m?i-m:m-j));
		if(best>val)best=val,ans=b[i];
		i=j+1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);n=2*n-1;
	for(int i=0;i<n;i++)scanf("%d",a+i);
	int l=1,r=n,ans=1;
	while(l<=r)
	{
		int m=(l+r)/2;
		if(f(m))l=m+1,ans=m;
		else r=m-1;
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main()
{
  string s; cin >> s;
  int y = stoi(s.substr(0, 4));
  int m = stoi(s.substr(5, 2));
  int d = stoi(s.substr(8, 2));

  if ((y < 2019) or (y == 2019 and m <= 4 and d <= 30)) {
    cout << "Heisei" << endl;
  } else {
    cout << "TBD" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  double N,K;
  double SUM;
  std::cout<<std::fixed<<std::setprecision(12);
  cin>>N>>K;
  for(int i=1;i<=N;i++){
    int sum=i;
    int two=1;
    while(sum<K){
      sum*=2;
      two*=2;
    }
    SUM+=1/(N*two);
  }
  cout<<SUM<<endl;
  

}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void) {
	long a,b,i;
		
	while( scanf("%ld %ld", &a, &b) != EOF ) {
	
		long G=1,L=1;
	
		if(a<b) {
			long tmp = a;
			a = b;
			b = tmp;
		}
		
		G=a*b;
		//a>=bの状態
		
		while(b%2==0 && a%2==0) {
			L *= 2;
			b/=2;
			a/=2;
		}
		
		
		i=b;
		while(i > 2) {
			if(b%i==0 && a%i==0) {
					L *= i;
					b /= i;
					a /= i;
			}
			else i = i-2;
		}
		
		G /= L;
		
		printf("%ld %ld\n", L, G);
	}
	return 0;		
}	

Measured memory_bytes: 596
// Author            -  Ranadev Varma
// Codeforces Handle -  Ranadev_CaptainR
// Codechef Handle   -  ranadev
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("O2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("unroll-loops")
 
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <iterator>
#include <iomanip>
#include <set>

using namespace std ;

#define MOD 1000000007LL
#define LOD 1000000006
#define pi 3.14159

#define lol1 ios::sync_with_stdio(false)
#define lol2 cin.tie(NULL);cout.tie(NULL)

#define FOR(i,a,b)  for(int i = a ; i < b ; i++)
#define RFOR(i,a,b) for(int i = a ; i > b ; i--)

#define pb push_back
#define mp make_pair
#define fi first
#define se second

int main()
{
    lol1;
    lol2;
    int a,b;
    cin >> a >> b;
    cout << a*b - (a*1) - (b*1) + 1 << "\n";
    return 0;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "2", "1 3 1 2" ].parse.expand.solve == 3 );
	assert( [ "5", "100 1 2 3 14 15 58 58 58 29" ].parse.expand.solve == 135 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto ls = input.front.split.to!( long[] );
	return tuple( ls );
}

auto solve( long[] ls )
{
	ls.sort();
	
	auto ans = 0L;
	for( auto i = 0L; i < ls.length; i += 2 ) ans += ls[ i ];
	return ans;
}


Measured memory_bytes: 256
#!usr/bin/env python3

import sys


class Die:
    def __init__(self, pips):
        self.pips = pips

    def move_die(self, direction):
        tmp = int()
        if direction == 'N':
            tmp = self.pips[0]
            self.pips[0] = self.pips[1]
            self.pips[1] = self.pips[5]
            self.pips[5] = self.pips[4]
            self.pips[4] = tmp
        elif direction == 'S':
            tmp = self.pips[0]
            self.pips[0] = self.pips[4]
            self.pips[4] = self.pips[5]
            self.pips[5] = self.pips[1]
            self.pips[1] = tmp
        elif direction == 'E':
            tmp = self.pips[0]
            self.pips[0] = self.pips[3]
            self.pips[3] = self.pips[5]
            self.pips[5] = self.pips[2]
            self.pips[2] = tmp
        elif direction == 'W':
            tmp = self.pips[0]
            self.pips[0] = self.pips[2]
            self.pips[2] = self.pips[5]
            self.pips[5] = self.pips[3]
            self.pips[3] = tmp

    def print_upside(self):
        print(self.pips[0])


def main():
    pips = [int(pip) for pip in sys.stdin.readline().strip('\n').split()]
    die = Die(pips)
    directions = list(sys.stdin.readline().strip('\n'))

    for direction in directions:
        die.move_die(direction)

    die.print_upside()


if __name__ == '__main__':
    main()

Measured memory_bytes: 7760
#import sys
#input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( lambda x:-x, map( int, input().split())))
    heapq.heapify(A)
    for _ in range(M):
        a = heapq.heappop(A)
        a = -((-a)//2)
        heapq.heappush(A, a)
    print( -sum(A))
if __name__ == '__main__':
    main()


Measured memory_bytes: 14180
#include<iostream>
#include<algorithm>
using namespace std;
int N_MAX = 200000;
int main()
{
  int n,i;
  int a[N_MAX];
  cin >> n;
  for(i=0;i<n;i++)
    cin >> a[i];
  sort(a,a+n);
  for(i=1;i<n;i++)
    if(a[i-1]==a[i]){
      cout << "NO" << endl;
      return 0;
    }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
	int page, n;
	string word;
	typedef map<string, map<int,int> > Dic;
	Dic dic;
	Dic::iterator ite1;
	map<int,int>::iterator ite2;
	while(cin >> word >> page)
	{
		dic[word][page]++;
	}
	for(ite1=dic.begin();ite1!=dic.end();++ite1)
	{
		cout << ite1->first << endl;
		n = 0;
		for(ite2=ite1->second.begin(); ite2 != ite1->second.end(); ++ite2)
		{
			if(n++) cout<< ' ';
			cout << ite2->first;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 0
# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

N = int(input())
a = list(map(int,input().split()))
l = lcm(a[0],a[1])
for i in range(2,N):
    l = lcm(l,a[i])
ans = 0
for i in range(N):
    ans += (l-1)%a[i]
print(ans)


Measured memory_bytes: 3316
import collections

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

c = collections.Counter(a_list)
c_set = set(a_list)
check = -1
check_list = []

if len(c) == 1:
    if c[0] != 0:
        print("Yes")
        exit()
elif len(c) == 2:
    if c[0] == n//3:
        print("Yes")
        exit()
elif len(c) == 3:
    for i in c_set:
        check_list.append(i)
        if check == -1:
            check = c[i]
        else:
            if check != c[i]:
                print("No")
                exit()
    else:
        res = check_list[0] ^ check_list[1] ^ check_list[2]
        if res == 0:
            print("Yes")
            exit()
        
print("No")

Measured memory_bytes: 14468
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define mod 1000000007
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define N 500055
#define int ll
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,h,w,t,vis[N],cnt,c[N];
struct xx{
	int x,y;
}z[N];
bool cmp(xx a,xx b){
	return (a.x==b.x)?a.y<b.y:a.x<b.x;
}
set <int> q;
set<int>::iterator it;
signed main(){
	h=read();w=read();n=read();
	F(i,1,n) z[i].x=read(),z[i].y=read();
	sort(z+1,z+n+1,cmp);
	q.insert(0);
	t=1;
	F(i,1,h){
		int p=t;
		for (;z[t].x==i;t++){
			if (vis[z[t].y]){
				wrn(i-1);return 0;
			}
		}
		cnt=0;
		for (it=q.be;it!=q.en;it++){
			if (vis[(*it)+i]) c[++cnt]=(*it);
			vis[(*it)+i]=1;
		}
		F(j,1,cnt) q.erase(c[j]);		
		t=p;
		for (;z[t].x==i;t++){
			vis[z[t].y]=0;
			if (q.find(z[t].y-i)!=q.en) q.erase(z[t].y-i);
			if (vis[z[t].y-1]) q.insert(z[t].y-i-1);
		}
	}
	wrn(h);
	return 0;
}

Measured memory_bytes: 8448
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int n,s[1000],p[1000],q[1000],r[1000],c,P,Q,R,C,i,cnt,cnt2,cnt3[1000];
	cnt=0;
	cnt2=0;
	while(1){
		cin>>n;
		if(n==0) break;
		for(i=0;i<n;i++){
			cin>>s[i]>>p[i]>>q[i]>>r[i];
		}
		cin>>P>>Q>>R>>C;
		for(i=0;i<n;i++){
			c=p[i]*4+q[i]*9+r[i]*4;
			if(p[i]<=P && q[i]<=Q && r[i]<=R && c<=C) cout<<s[i]<<endl;
			else cnt=cnt+1;
		}
		if(cnt==n) cout<<"NA"<<endl;
		cnt=0;
	}
	
	return 0;
}



Measured memory_bytes: 3100
N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 1 << 30
dp = [INF]*N
dp[0] = 0
for i, (d, h) in enumerate(zip(dp, H)):
    for k in range(1, K+1):
        if i+k >= N:
            break
        dp[i+k] = min(dp[i+k], d + abs(H[i+k]-h))

print(dp[-1])


Measured memory_bytes: 56032
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
#include <queue>
//#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
//input
int main(void)
{
    lli N, D;
    cin >> N >> D;
    lli x, y;
    lli cnt = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> x >> y;
        if (x * x + y * y <= D * D)
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define all(x) begin((x)), end((x))
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}

struct v {
    ll k;
    ll rem;
    ll x;
    ll y;
    ll dir;
    v(ll k, ll rem, ll x, ll y, ll dir) : k(k), rem(rem), x(x), y(y), dir(dir){

    }
    bool operator<(const v& right) const {
        return k == right.k ? rem > right.rem : k < right.k;
    }
    bool operator>(const v& right) const {
        return k == right.k ? rem < right.rem : k > right.k;
    }
};

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w,k;cin>>h>>w>>k;
    ll x[2],y[2];cin>>x[0]>>y[0]>>x[1]>>y[1];
    x[0]--;y[0]--;x[1]--;y[1]--;
    vector<string> mat(h);
    rep(i,h) {
        cin>>mat[i];
    }
    vector<vector<vector<v>>> cost(h, vector<vector<v>>(w, vector<v>(4, v(1e+15, 0,-1,-1,-1))));
    vector<vector<vector<bool>>> chk(h, vector<vector<bool>>(w, vector<bool>(4, false)));
    priority_queue<v, vector<v>, greater<v>> pq;
    rep(i,4) {
        cost[x[0]][y[0]][i] = v(0,0,x[0],y[0],i);
    }
    rep(i,4) {
        pq.emplace(0,0, x[0], y[0], i);
    }
    while(!pq.empty()) {
        v now = pq.top();

        ll nx = now.x,ny = now.y, dir = now.dir;
        ll nk = now.k, nrem = now.rem;
        pq.pop();
        if (chk[nx][ny][dir]){
            continue;
        }
        // if (cost[nx][ny][dir] < now){
        //     continue;
        // }
        chk[nx][ny][dir] = true;
        v next = v(0,0,0,0,0);
        if (nx<h-1&&mat[nx+1][ny]=='.') {
            next = (dir==0 && nrem>0) ? v(nk,nrem-1, nx+1,ny,0) : v(nk+1,k-1, nx+1,ny,0);
            if(chmin(cost[nx+1][ny][0], next)) {
                pq.push(next);
            }
        }
        if (ny<w-1&&mat[nx][ny+1]=='.') {
            next = (dir==1 && nrem>0) ? v(nk,nrem-1, nx,ny+1,1) : v(nk+1,k-1, nx,ny+1,1);
            if(chmin(cost[nx][ny+1][1], next)) {
                pq.push(next);
            }
        }
        if (ny>0&&mat[nx][ny-1]=='.'){
            next = (dir==2 && nrem>0) ? v(nk,nrem-1, nx,ny-1,2) : v(nk+1,k-1, nx,ny-1,2);
            if(chmin(cost[nx][ny-1][2], next)) {
                pq.push(next);
            }
        }
        if (nx>0&&mat[nx-1][ny]=='.') {
            next = (dir==3 && nrem>0) ? v(nk,nrem-1, nx-1,ny,3) : v(nk+1,k-1, nx-1,ny,3);
            if(chmin(cost[nx-1][ny][3], next)) {
                pq.push(next);
            }
        }
    }
    ll res = ll(1e+15);
    rep(i,4) {
        chmin(res, cost[x[1]][y[1]][i].k);
    }
    cout << (res == ll(1e+15) ? -1 : res) << endl; 
    return 0;
}


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

using namespace std;

const int MaxN = 5e3 + 5;

int n, A, B;
int pos[MaxN], a[MaxN];
long long f[MaxN][MaxN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> A >> B;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }
    memset(f, 100, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (pos[i] > pos[j])
            {
                f[i + 1][j] = min(f[i + 1][j], f[i][j] + B);
                f[i + 1][i] = min(f[i][j], f[i + 1][i]);
            }
            else
            {
                f[i + 1][j] = min(f[i + 1][j], f[i][j] + A);
            }
        }
    }
    long long res = *min_element(f[n + 1], f[n + 1] + n + 1);
    cout << res;
    return 0;
}


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



int main() {
    int N;
    cin>>N;
    vector<vector<int>> tree(N,vector<int>(0));
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        --a;--b;
        tree.at(a).push_back(b);
        tree.at(b).push_back(a);
    }
    vector<int> AB(N);//1つおきに1と-1で標識する
    queue<int> q;
    AB.at(0)=1;
    q.push(0);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(auto x:tree.at(v)){
            if(AB.at(x)==0){
                AB.at(x)=AB.at(v)*(-1);
                q.push(x);
            }
        }
    }
    int cnta=0,cntb=0;
    rep(i,N){
        if(AB.at(i)==1){cnta++;}
        else{cntb++;}
    }
    if(cnta>cntb){
        swap(cnta,cntb);
        rep(i,N){
            AB.at(i)*=(-1);
        }
    }
    
    vector<int> ans(N);
    vector<int> fora(0),forb(0);
    //case1
    if(cnta*2<cntb){
        
        rep(i,N){
            if(fora.size()<cnta && (i+1)%3==0){fora.push_back(i+1);}
            else{forb.push_back(i+1);}
        }
    }
    //case2
    else{
        for(int i=0;3*i+1<=N;i++){
            fora.push_back(3*i+1);
        }
        for(int i=0;3*i+2<=N;i++){
            forb.push_back(3*i+2);
        }
        for(int i=1;3*i<=N;i++){
            if(fora.size()<cnta){fora.push_back(3*i);}
            else{forb.push_back(3*i);}
        }
    }
    int nowa=0,nowb=0;
    rep(i,N){
        if(AB.at(i)==1){ans.at(i)=fora.at(nowa);nowa++;}
        else{ans.at(i)=forb.at(nowb);nowb++;}
    }
    rep(i,N-1){
        cout<<ans.at(i)<<" ";
    }
    cout<<ans.at(N-1)<<endl;
}

Measured memory_bytes: 16884
#include <iostream>
#include <string>

using namespace std;

int main(){
	string str, d;
	int a, b, n;
	cin >> str >> n;
	
	for(int i = 0; i < n; i++){
		cin >> d >> a >> b;
		string p;
		if(d == "print"){
			for(int j = a; j <= b; j++){
				cout << str[j];
			}
			cout << endl;
		}
		else if(d == "reverse"){
			p = str;
			for(int j = 0; j <= b - a; j++){
				str[a + j] = p[b - j];
			}
		}
		else if(d == "replace"){
			cin >> p;
			for(int j = 0; j <= b - a; j++){
				str[a + j] = p[j];
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 3188
$<.gets
$<.readlines.map(&:chomp).each do |line|
  s1 = /^>'(=+)#(=+)~$/.match(line)
  s2 = /^>\^(Q=)+~~$/.match(line)
  str = if s1 and s1[1] == s1[2]
    "A"
  elsif s2
    "B"
  else
    "NA"
  end
  puts str
end


Measured memory_bytes: 7284
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int a[60][60];
signed main()
{
    int h,w;
    cin >> h>>w;
    vector<string> s(h);
    for (int i = 0; i < h; i++)
    {
        cin >> s[i];
    }
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if(s[i][j]=='#'){
                continue;
            }
            int cnt = 0;
            for (int dx = -1; dx <= 1; dx++)
            {
                for (int dy = -1; dy <=1 ; dy++)
                {
                    if(dx*dx+dy*dy==0 || i+dx <0 || i+dx >=h || j+dy<0 || j+dy >w){
                        continue;
                    }
                    if(s[i+dx][j+dy]=='#'){
                        cnt++;
                    }
                                }
            }
            a[i][j] = cnt;
        }
    }
    
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if(s[i][j]=='.'){
                cout << a[i][j];
            }
            else{
                cout << s[i][j];
            }
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int ans=0;
    vector<int> a;
    cin >> n;
    for(int i=0;i<n;i++){
        int num;
        cin >> num;
        a.push_back(num);
    }

    for(int i=0;i<n;i++){
        int num = a[i];
        while(num !=0){
            if(num%2==0){
                num /= 2;
                ans++;
            }
            else{
                num =0;
            }
        } 
    }

    cout <<ans << endl;
}

Measured memory_bytes: 384