akhauriyash/Code-Regression huggingface dataset:
S = gets.chomp
N = S.size

current = S[0]
ans = Array.new(S.size) {1}
S.chars.each_with_index do |s, i|
  if S[i] == 'R'
    if i + 1 < N && S[i+1] == S[i]
      if i + 2 < N
        ans[i+2] += ans[i]
        ans[i] = 0
      else
        next
      end
    end
  end
end

(N-1).downto(0) do |i|
  if S[i] == 'L'
    if i - 1 >= 0 && S[i-1] == S[i]
      if i - 2 >= 0
        ans[i-2] += ans[i]
        ans[i] = 0
      else
        next
      end
    end
  end
end

puts ans.join(' ')


Measured memory_bytes: 10748
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1LL << 60;
const int MOD = 1'000'000'007;

template <typename T>
void print(const T &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

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

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

const int MAX = 100010;
ll dp[110][MAX];

int main()
{
    int n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
    }

    dp[0][0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int sum_w = 0; sum_w <= W; sum_w++)
        {
            if (sum_w < w[i])
            {
                dp[i + 1][sum_w] = dp[i][sum_w];
            }
            else
            {
                dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i]);
            }
        }
    }
    cout << dp[n][W] << endl;
    return 0;
}

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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {

    long long int n;
    cin >> n;

    long long int p[214514] = {};
    for ( long long int i = 1; i < n; i++ ) {
        long long int in;
        cin >> in;
        in--;
        p[in]++;
    }

    for ( long long int i = 0; i < n; i++ ) {
        cout << p[i] << endl;
    }

    return 0;

}


Measured memory_bytes: 5308
#include<iostream>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);
    
    int r, g, b, n;
    cin >> r >> g >> b >> n;

    int ans = 0;
    for (int x = 0; x <= n / r; x++) {
        int max_y = (n - r * x) / g;
        for (int y = 0; y <= max_y; y++) {
            if ((n - r * x - g * y) % b == 0) ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3188
N, D = gets.split.map(&:to_i)
x = []
N.times do |i|
  x[i] = gets.split.map(&:to_i)
end
ans = 0
for i in 0...N
  for j in (i+1)...N
    z = (0...D).inject(0){|sum, k| sum += (x[i][k] - x[j][k]).abs ** 2} ** 0.5
    ans += 1 if z % 1 == 0
  end
end
puts ans

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

int main()
{
  ll n; cin >> n;
  vector<ll> a;

  rep(i,n) {
    ll tmp;cin >> tmp;
    a.push_back(tmp);
  }

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

  cout << a[a.size()-1] - a[0] << endl;
  return 0;
}

Measured memory_bytes: 256
/*
    Created by Rahul Goel.
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*******************************************************************************/
using namespace std;
using namespace __gnu_pbds;
template < typename T >
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*******************************************************************************/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const int INF = 1e9;
const ll LINF = 1e18;
/*******************************************************************************/
ll mod_sum() { return 0LL; }
template < typename T, typename... Args >
T mod_sum(T a, Args... args) { return ((a + MOD_sum(args...))%MOD + MOD)%MOD; }
/*******************************************************************************/
ll mod_prod() { return 1LL; }
template< typename T, typename... Args >
T mod_prod(T a, Args... args) { return (a*MOD_prod(args...))%MOD; }
/*******************************************************************************/
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c)          (c).begin(), (c).end()
#define present(c,x)    ((c).find(x) != (c).end())
#define cpresent(c,x)   (find(all(c),x) != (c).end())
#define uniq(c)         (c).resize(distance((c).begin(), unique(all(c))))
#define min_pq(t)       priority_queue < t, vector < t >, greater < t > >
#define max_pq(t)       priority_queue < t >
#define pb              push_back
#define ff              first
#define ss              second
/*******************************************************************************/
using pii = pair < ll, ll >;
using vi = vector < ll >;
using vb = vector < bool >;
using vvi = vector < vector < ll > >;
using vvb = vector < vector < bool > >;
using vpii = vector < pii >;
using vvpii = vector < vector < pii > >;
/*******************************************************************************/
//.-.. . -. -.- .- .. ... .-.. --- ...- .
/*
    Code begins after this.
*/

ll solve() {
    ll n;
    cin >> n;
    if (n >= 30) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

signed main() {
    fastio;

    ll t = 1;
    while (t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3648
import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
d2 = sorted([x for x in d.keys()],reverse=True)
for m in d2:
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
print(res)

Measured memory_bytes: 34464
#include <cstdio>
#include <cstring>
#define ll long long int
#define LOWBIT(n) ((n)&(-n))
#define MAXN 200010

int N;
int A[MAXN];
int BIT[MAXN];

void update( int i, int k ){
        for( ; i <= N; i += LOWBIT(i) ){
                BIT[i] += k;
        }
}

ll getSum( int i ){
        ll res = 0;
        for( ; i >= 1 ; i -= LOWBIT(i)){
                res += BIT[i];
        }
        return res;
}

int main(){
        scanf("%d", &N );

        int t;
        for( int i = 1; i <= N; i++ ){
                scanf("%d", &t );
                A[i] = N+1 - t;
        }

        memset( BIT, 0, sizeof(BIT));

        int count = 0;
        for( int i = 1; i <= N; i++ ){
                update( A[i], 1 );
                //for( int j = 1; j <= N; j++ ) printf("%d ", BIT[j]);
                //printf("getSum = %lld", getSum(A[i]));
                //printf("\n");

                if( i == getSum(A[i]) )
                        count++;
        }

        printf("%d\n", count);
        return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Go_ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
#define PII pair<ll ,ll>
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
 
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const ll  MAX=1e18+500;
const int sz=1e3+100;


int main()
{
    Go_
    ll a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,n,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    int last=1;
    
    ll R,S,P;
    
    cin>>n>>m;
    cin>>R>>S>>P;
    cin>>str;
    pair<char,ll> ara[n];
    
    ll ans=0;
    
    for(i=1;i<=m;i++)
    {
        for(j=i;j<=n;j+=m)
        {
            if(i==j){
                if(str[j-1]=='r') ara[j-1].f='p',ara[j-1].s=1,ans+=P;
                else if(str[j-1]=='p') ara[j-1].f='s',ara[j-1].s=1,ans+=S;
                else ara[j-1].f='r',ara[j-1].s=1, ans+=R;
            }

            else{
                char ch;
                
                if(str[j-1]=='r') ch='p';
                else if(str[j-1]=='p')  ch='s';
                else ch='r';

                if(ch==ara[j-m-1].first){
                    if(ara[j-m-1].second % 2 == 0){
                        if(ch=='r') ans+=R;
                        else if (ch=='s') ans+=S;
                        else ans+=P;
                    }
                    ara[j-1].f=ara[j-m-1].f,ara[j-1].s=ara[j-m-1].s+1;
                }
                else{
                    if(ch=='r') ans+=R;
                    else if(ch=='s') ans+=S;
                    else ans+=P;
                    ara[j-1].f=ch,ara[j-1].s=1;
                }
            }

        
        }
      
    }


    cout<<ans<<endl;

}

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

int MOD=1000000007;
int modpow(int a,int x){
  if(a<0)a+=MOD;
  int ans=1;
  while(x>0){
    if(x&1) ans=ans*a%MOD;
      a=a*a%MOD;
      x>>=1;
  }
  return ans;
}

int gyaku(int n){
    return modpow(n,MOD-2);
}
////////////////////////////////////////////////////////////

int pati(int n,int i){
  if(n==0&&i==1)return 1;
  if(i==0)return 0;
  if(i<=pow(2,n+1)-2) return pati(n-1,i-1);
  if(i==pow(2,n+1)-1) return pow(2,n);
  if(i>=pow(2,n+1)&&i!=pow(2,n+2)-3) return pow(2,n)+pati(n-1,i-(pow(2,n+1)-1));
  if(i==pow(2,n+2)-3) return pow(2,n+1)-1;
}
signed main() {
  int n,x;
  cin>>n>>x;
  cout<<pati(n,x)<<endl;
  }


Measured memory_bytes: 4056
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n),f(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    cin >> f[i];
  }
  sort(a.begin(),a.end());
  sort(f.begin(),f.end(),greater<ll>());
  ll left=-1,right=1e12+5;
  while(left+1<right){
    ll mid=(left+right)/2;
    ll cnt=0;
    for(int i=0;i<n;i++){
      if(a[i]*f[i]>mid){
        cnt+=a[i]-mid/f[i];
      }
    }
    if(cnt<=k){
      right=mid;
    }
    else{
      left=mid;
    }
  }
  cout << right << endl;
}

Measured memory_bytes: 3328
def main():
  n,m = map(int,input().split())
  A = [int(input()) for _ in range(n)]
  V = [0 for _ in range(n)]
  for i in range(m):
    b = int(input())
    for j in range(n):
      if A[j] <= b:
        V[j] += 1
        break
  print(V.index(max(V)) + 1)

main()


Measured memory_bytes: 5620
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
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 (b<a) {a=b; return 1;} return 0;}

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...)
#define print(...)
#endif

int main() {
    int n; cin >> n;
    if (n==0) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> a(60, 0);
    rep(i, 60) {
        a[i] += pow(-2, i);
        if (i<58) a[i+2] = a[i];
    }
    debug(a);
    int start;
    rep(i, 60) if (((a[i]>=0)==(n>=0))&&(abs(a[i])>=abs(n))) {
        start = i;
        break;
    }
    string s;
    for (ll i = start; i >= 0; i--) {
        if (i==start) {
            n -= pow(-2, i);
            s += '1';
        } else {
            ll x = pow(-2, i);
            ll y = x/4;
            debug(x, abs(n-x), abs(n), abs(y));
            // if (abs(n-x)<=abs(n) || (n==-1 && i==1)) {
            // if (abs(n)>=abs(y)) {
            if ((i>1&&(a[i]>=0)==(n>=0)&&abs(n)>abs(a[i-2]))||(abs(n-x)<=abs(n))||(n==-1&&i==1)) {
                n -= x;
                s += '1';
            } else {
                s += '0';
            }
        }
        debug(i, pow(-2, i), n, s);
    }

    cout << s << endl;
    // ll tmp = 0;
    // rep(i, sz(s)) {
    //     if (s[i]=='1') tmp += pow(-2, sz(s)-i-1);
    // }
    // cout << tmp << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define show(x) cout<<x<<'\n'
#define showh(x) cout<<x<<' '
#define go(i,a,n) for(ll i=a;i<n;i++)
#define gor(i,a,n) for(ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
bool prime[100001];

bool ispoweroftwo(ll x)
{
    return x && !(x & (x-1));
}
ll xorcal(ll n)
{
    if(n%4==0)
        return n;
    if(n%4==1)
        return 1;
    if(n%4==2)
        return n+1;
    if(n%4==3)
        return 0;
}
void sieve(ll n)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(ll i=2;i*i<=n;i++)
    {
        if(prime[i]==true)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                prime[j]=false;
            }
        }
    }
    show(prime[89]);
}
bool isprime(ll n)
{
    if (n<=1) return false;
    if (n<=3) return true;

    if(n%2==0 or n%3==0) return false;

    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0 or n%(i+2)==0) return false;
    }
    return true;
}

ll modinverse(ll a,ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
      return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m; a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
       x += m0;

    return x;
}

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

ll power(ll A, ll B)
{
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;

    ll y;
    if (B % 2 == 0) {
        y = power(A, B / 2);
        y = (y * y) % mod;
    }

    else {
        y = A % mod;
        y = (y * power(A, B - 1) % mod) % mod;
    }

    return (ll)((y + mod) % mod);
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll count=0;
    go(i,1,n+1)
    {
        string s = to_string(i);
        if((ll)s.size()&1)
        {
            count++;
        }
    }
    show(count);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int mod=1e9+7;
int main(){
    int h,w;
    cin>>h>>w;
    char ch[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++)
        cin>>ch[i][j];
    }
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for(int i=1;i<h;i++){
    if(ch[i][0]=='#')
    dp[i][0]=0;
    else dp[i][0]=dp[i-1][0];
    }
    for(int j=1;j<w;j++){
        if(ch[0][j]=='#')
        dp[0][j]=0;
        else dp[0][j]=dp[0][j-1];
    }
    
    for(int i=1;i<h;i++){
        for(int j=1;j<w;j++){
            if(ch[i][j]=='.'){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
            dp[i][j]%=mod;
            }
        }
    }
    cout<<dp[h-1][w-1];
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define int long long
   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; }
    const int MAX =200005;
const int MOD =1000000007;
int par[MAX],Rank[MAX],sz[MAX],ans=1,z;
vector<int>cl[MAX],p[MAX];
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        Rank[i]=0;
        sz[i]=1;
    }
}

int find(int x){
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(Rank[x]<Rank[y]){
        par[x]=y;
        sz[y]+=sz[x];
        sz[x]=0;
    }
    else{
        par[y]=x;
        if(Rank[x]==Rank[y])Rank[x]++;
        sz[x]+=sz[y];
        sz[y]=0;
    }
}
int 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 COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

     signed main(){
      int n,x,y;
      cin>>n>>x>>y;
      init(n);
      COMinit();
      int c,w;
      for(int i=0;i<n;i++){
          cin>>c>>w;c--;
          cl[c].push_back(w);
          p[c].push_back(i);
      }
      for(int i=0;i<n;i++)sort(cl[i].begin(),cl[i].end());
      for(int i=0;i<n;i++)for(int j=0;j<cl[i].size();j++)if(cl[i][0]+cl[i][j]<=x)unite(p[i][0],p[i][j]);
      int c1=-1,w1=MOD,c2=-1,w2=MOD;
      for(int i=0;i<n;i++)if(cl[i].size()!=0&&cl[i][0]<w2){
          if(cl[i][0]<w1){
              c2=c1;
          w2=w1;
          c1=i;
          w1=cl[i][0];
          }else{
              c2=i;
          w2=cl[i][0];
          }
          
        
      }
      int sc[n]={};
     
      if(c2!=-1){
        for(int i=0;i<n;i++){
            if(i!=c1){
                for(int j=0;j<cl[i].size();j++)if(cl[c1][0]+cl[i][j]<=y)sc[i]+=sz[p[i][j]];
            }else{
                sc[i]+=sz[p[i][0]];
                for(int j=1;j<cl[i].size();j++)if(cl[c2][0]+cl[i][j]<=y)sc[i]+=sz[p[i][j]];
            }
        }
        
        for(int i=1;i<n;i++){
            ans=(ans*COM(sc[i-1]+sc[i],sc[i]))%MOD;
            
            sc[i]+=sc[i-1];  
        }
        cout<<ans<<endl;    
    }else cout<<1<<endl;
      
      
   }
     


 


 






    





      

        


Measured memory_bytes: 32856
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;
int a,b;
int ans;

int main()
{
    cin>>a>>b;
    int now=1;
    while (now<b)
    {
        now-=1;
        now+=a;
        ans+=1;
    }
    cout<<ans<<endl;

    return 0;
}



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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vivi vector<vi>
const int INF = int(1e9);
typedef long long int ll;
/* -- template -- */

const ll MOD = 1e9 + 7;

ll modpow(int a, int b){//return a^b
    if(b == 0)return 1;
    while(b > 1){
        a = a * 2 % MOD;
        --b;
    }
    return a;
}

int main(){
    int N; cin >> N;
    int A[N]; rep(i, N)cin >> A[i];
    //2^N/2
    sort(A, A + N);
    bool flg = true;
    for(int i =((A[0] == 0) ? 1 : 0); i < N - 1; i += 2){
        if(A[i] != A[i + 1])flg = false;
    }
    if(flg){
        cout << modpow(2, N / 2) << endl;
    }else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 640
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = nc2(N)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in reversed(ans):
    print(v)

Measured memory_bytes: 59696
#include <iostream>

using namespace std;

int main(){
    int n, k, a = 1;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        if(a * 2 < a + k)
            a *= 2;
        else
            a += k;
        
    }
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

#define REP(i,n) for(int i = 0; i <= n; i++)
#define ll long long
#define PI 3.141592653589

using namespace std;

int main(void){
    int i, N, ans;
    cin >> N;
    bool flag = false;

    REP(i,N){
        if((int)(i * 1.08) == N){
            flag = true;
            ans = i;
        }
    }
    
    if(flag == true) cout << ans;
    else cout << ":(";
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 998244353;
const int INF = 1e18;

int dp[2010][4010];
int r[2010];
int b[2010];


struct Combination {
    vector<int64_t> fact, rfact;
    Combination(int sz) : fact(sz + 1), rfact(sz + 1) {
        fact[0] = 1;
        for(int i = 1; i < fact.size(); i++){
            fact[i] = fact[i - 1] * i % mod;
        }
        rfact[sz] = inv(fact[sz]);
        for(int i = sz - 1; i >= 0; i--){
            rfact[i] = rfact[i + 1] * (i + 1) % mod;
        }
    }
    int64_t inv(int x) const {
        return pow(x, mod - 2);
    }
    int64_t pow(int64_t x, int64_t n) const {
        int64_t ret = 1;
        while(n > 0){
            if(n & 1) (ret *= x) %= mod;
            (x *= x) %= mod;
            n >>= 1;
        }
        return (ret);
    }
    int64_t P(int n, int r) const {
        if(r < 0 || n < r) return (0);
        return (fact[n] * rfact[n - r] % mod);
    }

    int64_t C(int p, int q) const {
        if(q < 0 || p < q) return (0);
        return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
    }

    int64_t H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return (r == 0 ? 1 : C(n + r - 1, r));
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    rep(i, 0, n){
        if(i){
            r[i] = r[i - 1];
            b[i] = b[i - 1];
        }
        if(s[i] == '0') r[i] += 2;
        else if(s[i] == '2') b[i] += 2;
        else{
            r[i]++; b[i]++;
        }
    }
    dp[0][0] = 1;
    rep(i, 0, n){
        rep(j, 0, 2 * n + 1){
            if(dp[i][j] == 0) continue;
            int rr = r[i] - j;
            int bb = b[i] - (i - j);
            if(rr != 0) (dp[i + 1][j + 1] += dp[i][j]) %= mod;
            if(bb != 0) (dp[i + 1][j] += dp[i][j]) %= mod;
        }
    }
    int ans = 0;
    Combination cb(4010);
    rep(i, 0, 2 * n + 1){
        int rr = r[n - 1] - i;
        int bb = b[n - 1] - (n - i);
        if(dp[n][i] == 0) continue;
        int tmp = dp[n][i] * cb.C(n, rr) % mod;
        (ans += tmp) %= mod;
    }
    cout << ans << endl;
}

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

#define MAX_N 8
#define MAX_M 28


bool is_in(vector<int> array,int a){
	for(int i=0;i<array.size();i++){
		if(a==array[i])return true;
	}
	return false;
}


int main() {
    int n,m;
	cin >> n >> m;
	vector<int> p[MAX_N];
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >>b;
		a--;b--;
		p[a].push_back(b);
		p[b].push_back(a);
	}

	queue<vector<int> > q;
	int cnt = 0;
	vector<int> v;
	v.push_back(0);
	q.push(v);
	while(q.size()!=0){
		vector<int> v = q.front();
		q.pop();
		for(int i=0;i<p[v.back()].size();i++){
			int cand = p[v.back()][i];
			if(!is_in(v,cand)){
				if(v.size()==n-1){
					cnt++;
				}else{
					vector<int> v2(v.size());
					copy(v.begin(), v.end(), v2.begin());
					v2.push_back(cand);
					q.push(v2);
				}
			}
		}
	}
	
	cout << cnt << endl;
    return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	int N;
	cin >> N;
	set<string> st;
	for (int i = 0; i < N; ++i) {
		string s;
		cin >> s;
		st.insert(s);
	}

	cout << st.size() << endl;

	return 0;
}


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

signed main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	int w, h; cin >> w >> h;
	if(w == 1 || h == 1)
		cout << "1";
	else
		cout << (w * h + 1) / 2;

	

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int fcounter(int x){
    if(x==0) return 0;
    else{
        return fcounter(x >> 1) + (x & 1);
    }
}
int main(){
    int n;
    int a[20];
    int x[20][20], y[20][20];
    cin >> n;
    for(int i= 1; i <= n; i++){
        cin >> a[i];
        for(int j = 1; j <= a[i]; j++){
            cin >> x[i][j] >> y[i][j];
        }
    }
    
    int ans = 0;
    for(int bits = 1; bits < (1 << n); bits++){
        bool ok = true;
        for(int i = 1; i <= n; i++){
            if(!(bits & (1 << (i-1)))) continue;
            for(int j = 1; j <= a[i]; j++){
                if(((bits >> (x[i][j] - 1)) ^ y[i][j]) & 1) ok = false;
               
            }
        }
        if(ok) ans = max(ans, fcounter(bits));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define DICE_FACES 6
#define DICE_ROLL 7

typedef struct dice {
  int label[DICE_FACES];
  int top, front, right;
} Dice;
void roll(Dice *d, char direction) {
  int tmp = d->top;
  switch (direction) {
    case 'E' :
      d->top = DICE_ROLL - d->right;
      d->right = tmp;
      break;
    case 'W' :
      d->top = d->right;
      d->right = DICE_ROLL - tmp;
      break;
    case 'S' :
      d->top = DICE_ROLL - d->front;
      d->front = tmp;
      break;
    case 'N' :
      d->top = d->front;
      d->front = DICE_ROLL - tmp;
      break;
  }
}
void dice_init(Dice *d, int n[]) {
  int i;
  for (i = 0; i < DICE_FACES; i++) {
    d->label[i] = n[i];
  }
  d->top = 1;
  d->front = 2;
  d->right = 3;
}
int main(void) {
  int n[DICE_FACES];
  char ch[102];
  int i;
  for (i = 0; i < DICE_FACES; i++) scanf("%d", &n[i]);
  scanf("%s", ch);
  Dice dice;
  dice_init(&dice, n);

  i = 0;
  while(ch[i]) {
    roll(&dice, ch[i]);
    i++;
  }

  printf("%d\n", dice.label[dice.top - 1]);

  return 0;
}



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

int main(){
  int N,A,B;
  string S;
  cin >> N >> A >> B >> S;

  int cnt_ab=0;
  int cnt_b=0;
  for(int i=0;i<N;i++){
    if(S.at(i)=='a'){
      if(cnt_ab<A+B){
        cout << "Yes" << endl;
        cnt_ab++;
      }
      else  cout << "No" << endl;
    }
    else if(S.at(i)=='b'){
      if(cnt_ab<A+B && cnt_b<B){
        cout << "Yes" << endl;
        cnt_ab++;
        cnt_b++;
      }
      else  cout << "No" << endl;
    }
    else  cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define N 3010
ll dp[4][N][2];
int main(){
	int n, m;
	cin>>n>>m;
	rep(i, n+1) dp[0][i][i==0] = 1;
	rep(i, m){
		int t = i%2;
		rep(k, 2) rep(j, n+1) dp[t*2][j][k] %= mod;
		mset(dp[t*2+1], 0);
		mset(dp[(t*2+2)&3], 0);
		rep(k, 2){
			for(int j = 1; j <= n; j++) dp[t*2+1][j  ][k|(j-1==0)]+=dp[t*2][j][k];
			for(int j = 0; j <  n; j++) dp[t*2+1][j+1][k         ]+=dp[t*2][j][k];
		}
		rep(k, 2) for(int j = 1; j <= n; j++){
			dp[(t*2+2)&3][j][k]+=dp[t*2+1][j][k];
			dp[(t*2+2)&3][j-1][k]+=dp[t*2+1][j][k];
		}
	}
	ll res = 0;
	rep(j, n+1) (res+=dp[2*(m%2)][j][1])%=mod;
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

/*

*/

public class Main {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        int T = sc.nextInt();
        int S = sc.nextInt();

        if (D <= T * S) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35632
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
  ll n;
  cin>>n;
  bool f=false;
  for(int i=1;i<=9;i++)
  {
      if(n%i==0)
      {
          ll temp=n/i;
          if(temp>=1 && temp<=9)
          {
              f=true;
              break;
          }
      }
  }
  if(f)
    cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 256
package main

import(
	"fmt"
)

func main() {
	var a,b,c,d int
	fmt.Scan(&a,&b,&c,&d)
	
	
	for {
		c -= b
      //fmt.Println(c)
		if c  <= 0 {
			fmt.Println("Yes")
			return
		}
		a -= d
      //fmt.Println(a)
		if a  <= 0 {
			fmt.Println("No")
			return
		}
		
	}
}

Measured memory_bytes: 1752
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main(void){
    int n, p[105];
    string s[105];
    vector<string> city;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> p[i];
        city.push_back(s[i]);
    }
    sort(city.begin(), city.end());
    
    int ans[105], idx = 0, l = 0;
    while (idx < n) {
        vector<pair<int, int>> ge;
        int sub = 0;
        while (city[idx] == city[idx + sub] && idx + sub < n) sub++;
        for (int i = 0; i < n; i++) {
            if (s[i] == city[idx]) ge.emplace_back(p[i], i);
        }
        sort(ge.begin(), ge.end());
        for (int i = ge.size() - 1; i >= 0; i--) {
            ans[l] = ge[i].second;
            l++;
        }
        idx += sub;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << endl;
    }
    
    
    
}


Measured memory_bytes: 888
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAX_N = 100;

int key[MAX_N];

int main ( void )
{
	int n;
	while (cin >> n, n) {
		for (int i = 0; i < n; ++i) {
			cin >> key[i];
		}
		string s, out;
		cin >> s;
		for (int i = 0, I = s.size(); i < I; ++i) {
			char c = s[i];
			for (int j = 0, J = key[i%n]; j < J; ++j) {
				--c;
				if (c < 'A') {
					c = 'z';
				}
				else if ('Z' < c && c < 'a') {
					c = 'Z';
				}
			}
			out += c;
		}
		cout << out << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    rep3(i,N,1000){
        ll n3 = i/100;
        ll n2 = (i/10)%10;
        ll n1 = i%10;
        if(n1==n2 && n1 == n3){
            cout<<i<<endl;
            return 0;
        }
    }
    


    return 0;
    

}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main{

	public static void main(String args[]){

		Scanner sc = new Scanner(System.in);

		String st=sc.next();
		char n[]=st.toCharArray();

		for(int i=0;i<3;++i){
			if(n[i]=='9') n[i]='1';
			else if(n[i]=='1') n[i]='9';
		}

		System.out.print(n[0]);
		System.out.print(n[1]);
		System.out.println(n[2]);
	}
}



Measured memory_bytes: 23508
#include <cstdio>
 
int main(){
  int a,b,c,ans = 0;
 
  scanf("%d%d%d",&a,&b,&c);
  for(int i = a ; i <= b ; i++){
    if(c % i == 0) ++ans;
  }
  printf("%d\n",ans);
 
  return 0;
}

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

int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main() {
  int n, sum = 0;
  cin >> n;
  sum = findSumOfDigits(n);
  if (n % sum == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3588
# 全方位木DP

def resolve():
    def dfs1(r_topo, par):
        for idx in reversed(r_topo):
            for (to, cost) in G[idx]:
                if to == par[idx]:
                    continue
                dist[idx] = max(dist[idx], dist[to] + cost)

    def dfs2(idx, d_par, par):
        stack = [(idx, d_par, par)]
        while stack:
            idx, d_par, par = stack.pop()
            d_child = []
            d_child.append((0, -1))
            for (to, cost) in G[idx]:
                if to == par:
                    d_child.append((d_par + cost, to))
                else:
                    d_child.append((dist[to] + cost, to))
            d_child.sort(reverse=True)
            ans[idx] = d_child[0][0] + d_child[1][0]
            for (to, cost) in G[idx]:
                if to == par:
                    continue
                nx_d_par = d_child[d_child[0][1] == to][0]
                stack.append((to, nx_d_par, idx))

    N = int(input())
    if N == 1:
        return print(0)

    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, input().split())
        G[a].append((b, c))
        G[b].append((a, c))

    topo = []
    P = [-1] * N
    node = [0]
    while node:
        s = node.pop()
        topo.append(s)
        for (to, cost) in G[s]:
            if to == P[s]:
                continue
            P[to] = s
            node.append(to)

    dist = [0] * N
    ans = [0] * N
    dfs1(topo, P)
    dfs2(0, 0, -1)
    print(max(ans))


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 46768
if __name__ == "__main__":
    N, K = map(int, input().split())
    S = input()

    # まず最初の幸福な人数を数え、文字列を圧縮する
    res = 0
    for i in range(N-1):
        if S[i+1] == S[i]:
            res += 1

    res = min([res + 2 * K, N - 1])
    print(res)


Measured memory_bytes: 3316
#include <queue>
#include <tuple>
#include <cstdio>
#include <cstring>
using namespace std;
#define SENTINEL 99999
typedef tuple<int,int,int> tiii; //building, floor, depth
int M[2][101],B[2][101],n;
int bfs(int i){
memset(M,99,sizeof(M));
	queue<tiii> q;
	q.push(make_tuple(i,0,0));M[i][0]=0;
	for(;!q.empty();){
		tiii t=q.front();q.pop();
		int building=get<0>(t);
		int floor=get<1>(t);
		int depth=get<2>(t);
		for(;B[building][floor]==1&&B[building][floor+1]==1;){
			if(M[building][floor+1]>M[building][floor])M[building][floor+1]=M[building][floor];
			floor++;
		}
		for(;B[building][floor]==2;){
			if(M[building][floor-1]>M[building][floor])M[building][floor-1]=M[building][floor];
			floor--;
		}
		if(floor==n-1)return depth;
		for(i=2;i>=0;i--)if(floor+i<n&&M[building^1][floor+i]>M[building][floor]){
			M[building^1][floor+i]=M[building][floor];
			q.push(make_tuple(building^1,floor+i,depth+1));
		}
	}
	return SENTINEL;
}
int main(){
	int i,j;
	for(;scanf("%d",&n),n;){
		for(j=0;j<2;j++){
			for(i=0;i<n;i++)scanf("%d",B[j]+i),M[j][i]=SENTINEL;
			for(;i<101;i++)B[j][i]=0,M[j][i]=SENTINEL;
		}
		i=min(bfs(0),bfs(1));
		printf(i==SENTINEL?"NA\n":"%d\n",i);
	}
}

Measured memory_bytes: 1020
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
inf = 1000000007

ans = 1
cap = [0, 0, 0]
for i in range(N):
    tmp = 0
    for j in range(3):
        if cap[j] == A[i]:
            tmp += 1
    for j in range(3):
        if cap[j] == A[i]:
            cap[j] += 1
            break
    ans *= tmp
    ans %= inf

print(ans)


Measured memory_bytes: 52952
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A=0;
    int B=0;
    cin >>A>>B;
    if(A%3==0){
        cout<<"Possible"<<endl;
    }
    else if(B%3==0){
        cout<<"Possible"<<endl;
    }
    else if((A+B)%3==0){
        cout<<"Possible"<<endl;
    }
    else { cout<<"Impossible"<<endl;
    }
}

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

#define st first
#define nd second

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<ii> vii;
typedef vector<pll> vpll;

int main() {
    pll a, b, c, d;
    ll n;
    cin >> a.st >> b.st >> c.st >> d.st >> n;
    a.nd = 25, b.nd = 50, c.nd = 100, d.nd = 200;
    vpll v = {a, b, c, d};
    sort(v.begin(), v.end(), [] (pll a, pll b){
        return a.st*b.nd < b.st*a.nd;
    });
    n *= 100;
    ll ans = 0;
    for (auto x: v) {
        if (n < x.nd) continue;
        ans += (n / x.nd) * x.st;
        n %= x.nd;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		long x = scanner.nextLong();
		long ans = 0;
		long tmp = x / 11;
		if (x % 11 <= 6 && x % 11 != 0) {
			ans = tmp * 2 + 1;
		} else if (x % 11 == 0) {
			ans = tmp * 2;
		} else {
			ans = tmp * 2 + 2;
		}
		System.out.println(ans);

	}
}


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

int main(void) {
    unsigned int n, m, i;
    double x = 0, t, p;
    
    scanf("%u %u", &n, &m);

    t = (n - m) * 100 + 1900 * m;
    p = pow(0.5, m);

    for (i = 1; i < 1000000; i++) {
        x += t * i * pow(1 - p, i - 1) * p;
    }

    printf("%u\n", (unsigned int)(x + 0.5));
    
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const long long INF = 1LL << 60;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


int main() {
    ll N;
    cin>>N;
    vl dp(N);
    vl h(N);
    rep(i,N) cin>>h.at(i);
    rep(i,N) dp.at(i)=INF;
    dp.at(0)=0;
    dp.at(1)=abs(h.at(0)-h.at(1));
    rep(i,N){
        if(i>1){
        chmin(dp.at(i),dp.at(i-1)+abs(h.at(i)-h.at(i-1)));
        chmin(dp.at(i),dp.at(i-2)+abs(h.at(i)-h.at(i-2)));
        }
    }
    cout<<dp.at(N-1)<<endl;
}


Measured memory_bytes: 1792
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long 
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
  	int t;cin>>t;
  	map<string,int>mp;
  	while(t--)
  	{
  		string s;cin>>s;
		mp[s]++;  	
	}
	cout<<"AC x "<<mp["AC"]<<endl;
	cout<<"WA x "<<mp["WA"]<<endl;
	cout<<"TLE x "<<mp["TLE"]<<endl;
	cout<<"RE x "<<mp["RE"]<<endl;
   
    return 0;
}


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

int main() {
  int H, W, h, w;
  cin >> H >> W >> h >>w;
  cout << H * W - (H * w + W * h - h * w) << endl;
  return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 200000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

LL a[N];
int main() {
    LL n;
    scanf("%lld",&n);
    LL tot=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        tot+=a[i];
    }

    LL minn=1E15;
    LL sum=a[1];
    for(int i=2;i<=n;i++){
        LL last=tot-sum;
        LL sub=last-sum;
        sub=llabs(sub);
        minn=min(minn,sub);
        sum+=a[i];
    }
    printf("%lld\n",minn);

    return 0;
}


Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    val d = readLine()!!.replace(" ", "")


    fun check(c: Char): Boolean {
        return d.indexOf(c) == -1
    }

    var ans = n.toString()
    fun checkAll(s: String): Boolean {
        var ret = true
        for (i in 0 until s.length) {
            ret = ret && check(s[i])
        }
        return ret
    }

    var c = n
    while(true) {
        if (checkAll(ans) ) {
            println(c)
            break
        } else {
            c++
            ans = c.toString()
        }
    }
}


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

using int64 = long long;
using uint64 = unsigned long long;
using P = pair<int, int>;

const int MAX_H = 500;
const int MAX_W = 500;

int a[MAX_H][MAX_W];

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

    int H, W;
    cin >> H >> W;

    for (int r = 0; r < H; r++)
    {
        for (int c = 0; c < W; c++)
        {
            cin >> a[r][c];
        }
    }

    vector<pair<P, P>> operations;
    for (int r = 0; r < H; r++)
    {
        int dc = (r % 2 == 0) ? 1 : (-1),
            startC = (r % 2 == 0) ? 0 : (W - 1);

        for (int c = startC; 0 <= c and c < W; c += dc)
        {
            if (a[r][c] % 2 == 0) continue;
            if (r == H - 1 and ((c + dc) < 0 or (c + dc) >= W)) continue;

            int nr = r, nc = c + dc;
            if ((c + dc) < 0 or (c + dc) >= W)
            {
                nr = r + 1;
                nc = c;
            }
            a[r][c]--;
            a[nr][nc]++;
            operations.emplace_back(P(r + 1, c + 1), P(nr + 1, nc + 1));
        }
    }

    cout << operations.size() << endl;
    for (auto& op : operations)
    {
        auto from = op.first,
             to   = op.second;
        cout << from.first << " " << from.second << " " << to.first << " " << to.second << endl;
    }

    return 0;
}


Measured memory_bytes: 5232
#include <iostream>
using namespace std;
 
int balls[10];
 
bool dfs(int idx, int b, int c){
    if(idx > 9) return true;
     
    bool ok = false;
    if(b < balls[idx]) ok = dfs(idx+1, balls[idx], c);
    if(c < balls[idx]) ok = dfs(idx+1, b, balls[idx]);
    return ok;
}
 
int main() {
    int n; cin >> n;
    while(n--){
        for(int i = 0; i < 10; i++) cin >> balls[i];
	cout << (dfs(0, 0, 0) ? "YES" : "NO") << endl;
    }
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); \
                      cerr << "\n\n" << "Time elapsed: " << \
                      (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
                      return 0
#define ll long long int
#define ull unsigned long long int
#define db long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound 
#define pii pair<int , int>
#define pdd pair<db , db>
#define pll pair<ll , ll>
#define vpl vector<pll >
#define vll vector<ll >
#define mod 1000000007
#define mod1 998244353 
#define inf 1000000000000000007
#define eps 0.000001
#define stp fixed<<setprecision(20)
#define endl '\n'


int main()
{
    fastio;
    #ifdef APNA_IO
        start_routine();
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);    
    #endif

    ll n;cin>>n;
    ll a[n+1];
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    multiset<ll> m;

    for(ll i=n;i>0;i--)
    {
        auto p=(m.ub(a[i]));
        if(p==m.end())
        {
            m.insert(a[i]);
            continue;
        }

        ll x=*p;
        m.erase(m.find(x));
        m.insert(a[i]);
    }
    cout<<m.size();

    #ifdef APNA_IO
        end_routine();
    #endif
}


Measured memory_bytes: 5760
#include <stdio.h>
#include <string.h>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
	if(ch=='A') return 1;
	else if(ch=='C') return 2;
	else if(ch=='G') return 3;
	else if(ch=='T') return 4;
	else return 0;
}

long long getKey(char str[]){
	long long sum=0,p=1,i;
	for(i=0;i<strlen(str);i++){
		sum+=p*(getChar(str[i]));
		p*=5;
	}
	return sum;
}

int h1(int key){
	return key % M;
}

int h2(int key){
	return 1+(key % (M-1));
}

int find(char str[]){
	long long key,i,h;
	key = getKey(str);
	
	for(i=0;;i++){
		h = (h1(key) + i*h2(key)) % M;
		if(strcmp(H[h],str)==0) return 1;
		else if(strlen(H[h])==0) return 0;
	}
	return 0;
}

int insert(char str[]){
	long long key, i ,h;
	key = getKey(str);
	for(i=0;;i++){
		h = (h1(key)+ i*h2(key)) % M;
		if(strcmp(H[h],str) ==0) return 1;
		else if(strlen(H[h])==0) {
			strcpy(H[h],str);
			return 0;
		}
	}
}

int main(){
	int i,n,h;
	char str[L],com[9];
	for(i=0;i<M;i++) H[i][0]='\0';
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
	scanf("%s %s",com,str);
	
	if(com[0]=='i'){
		insert(str);
	}
	else {
		if(find(str)){
			printf("yes\n");
		}else {
			printf("no\n");
		}
	}
}
	return 0;
}

Measured memory_bytes: 14916