akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
#define DREP(i,a,b) for(int i=(a),ed=(b);i>=ed;--i)
typedef long long ll;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x; 
}

const int N=2e5+10;
int n,a[N],s[N],len[2],stk[2][N],mx[2][N],sum[2],maxn[N],sufsum[N];

int tr[N*50],ch[N*50][2],cnt;
struct SegmentTree{
    int rt[N];
    inline void pushup(int x){tr[x]=max(tr[ch[x][0]],tr[ch[x][1]]);}
    inline void Insert(int &p,int pre,int l,int r,int pos,int v){
	p=++cnt;if(l==r){tr[p]=max(tr[p],v);return;}
	int mid=(l+r)>>1;
	if(pos<=mid){ch[p][1]=ch[pre][1];Insert(ch[p][0],ch[pre][0],l,mid,pos,v);}
	else{ch[p][0]=ch[pre][0];Insert(ch[p][1],ch[pre][1],mid+1,r,pos,v);}
	pushup(p);
    }
    inline int Query(int p,int l,int r,int L,int R){
	if(!p||L>R)return 0;
	if(L<=l&&r<=R)return tr[p];
	int mid=(l+r)>>1,res=0;
	if(L<=mid)res=max(res,Query(ch[p][0],l,mid,L,R));
	if(mid<R)res=max(res,Query(ch[p][1],mid+1,r,L,R));
	return res;
    }
}T[2];

inline bool check(int op,int i){
    int ned=sum[op]+sufsum[i+1]-sum[op^1];
    if(ned<0)return 0;
    return T[ned&1].Query(T[ned&1].rt[i+1],1,n,mx[op^1][len[op^1]]+1,n)>=ned;
}

int main(){
//    freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    n=read();REP(i,1,n)a[i]=read(),maxn[i]=max(maxn[i-1],a[i]);
    DREP(i,n,1)sufsum[i]=sufsum[i+1]+(a[i]==maxn[i]);
    DREP(i,n,1){
	int t0=T[0].Query(T[0].rt[i+1],1,n,a[i]+1,n),t1=T[1].Query(T[1].rt[i+1],1,n,a[i]+1,n);
//	cout<<t0<<' '<<t1<<endl;
	if(a[i]==maxn[i]){
	    T[0].Insert(T[0].rt[i],T[0].rt[i+1],1,n,a[i],t0+2);
	    if(t1)T[1].Insert(T[1].rt[i],T[1].rt[i+1],1,n,a[i],t1+2);
	    else T[1].rt[i]=T[1].rt[i+1];
	}
	else{
	    T[1].Insert(T[1].rt[i],T[1].rt[i+1],1,n,a[i],t0+1);
	    if(t1)T[0].Insert(T[0].rt[i],T[0].rt[i+1],1,n,a[i],t1+1);
	    else T[0].rt[i]=T[0].rt[i+1];
	}
    }
    REP(i,1,n){
	s[i]=-1;
	REP(j,0,1){
	    stk[j][++len[j]]=a[i];
	    mx[j][len[j]]=max(mx[j][len[j]-1],a[i]);
	    sum[j]+=(mx[j][len[j]]==a[i]);
	    if(check(0,i)){s[i]=j;break;}
	    if(check(1,i)){s[i]=j;break;}
	    sum[j]-=(mx[j][len[j]]==a[i]);
	    --len[j];
	}
	if(!~s[i]){puts("-1");return 0;}
    }
    REP(i,1,n)printf("%d",s[i]);
    puts("");
    return 0;
}


Measured memory_bytes: 103040
#include <bits/stdc++.h>
    
using namespace std;
typedef long long ll;
    
int main()
{
    int X;
    cin >> X;
    vector<bool> e(X+1);

    e[1] = true;
    for (int b = 2; b <= X; b++) {
        int v = b * b;
        while (v <= X) {
            e[v] = true;
            v *= b;
        }
    }
    for (int i = X; 1 <= i; i--) {
        if (e[i]) {
            cout << i;
            return 0;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T1, class T2>bool chmax(T1& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<class T1, class T2>bool chmin(T1& a, const T2& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int a;
    string s;
    cin >> a >> s;

    if (a >= 3200) {
        write(s);
    }
    else {
        write("red");
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    ull N;
    cin>>N;
    ull d=1,bef=0;
    bool f0=false,fo=false;
    REP(i,N){
        ull t;
        cin>>t;
        if(t==0){
            f0=true;
        }
        d*=t;
        if(d>1000000000000000000||d==0){
            fo=true;
        }
    }
    if(f0){
        cout<<0;return 0;
    }else if(fo){
        cout<<-1;return 0;
    }else
    cout<<d;
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
   /* #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        

fast();
//ll t;cin>>t;while(t--)
{
    ll n,inc=0;
    cin>>n;
    ll a[n],b[n];
    for(int i=0;i<n;i++)
    {
      cin>>a[i]>>b[i];
    }
    for(int i=n-1;i>=0;i--)
    {
      if((a[i]+inc)%b[i]==0)
        continue;
      else
      {
        ll ext=ceil((a[i]+inc)/double(b[i]));

        ll cur=ext*b[i];
        inc+=(cur-(a[i]+inc));
       // cerr<<ext<<" "<<cur<<" "<<inc<<endl;

      }
    }
    cout<<inc<<endl;
}
return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const int inf=1e5+10;

int n,m,ind;
vector<vector<int>> g(100010),g2(100010);
vector<bool> used(100010,false);
vector<int> v,v2(100010),v3(100010),ans(100010);

void dfs(int now){
  if(used[now]) return;
  used[now]=true;
  for(auto itr:g[now]) dfs(itr);
  v.push_back(now);
  v2[now]=ind;
  v3[ind--]=now;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    ind=n;
    rep(i,n+m-1){
      int a,b;
      cin>>a>>b;
      g[a].push_back(b);
      g2[b].push_back(a);
    }
    FOR(i,1,n+1) if(!used[i]) dfs(i);
    FOR(i,1,n+1){
      int cnt=0;
      for(auto itr:g2[i]){
        cnt=max(cnt,v2[itr]);
      }
      ans[i]=v3[cnt];
    }
    FOR(i,1,n+1) cout<<ans[i]<<endl;
}

Measured memory_bytes: 16636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS=1e-10;
const ll INF=1000000000;
int main(){
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        string s;
        cin>>s;
        set<string> st;
        int n=s.length();
        for(int i=0;i<n;i++){
            string s1=s.substr(0,i);
            string s2=s.substr(i);
            st.insert(s1+s2);
            st.insert(s2+s1);
            reverse(s1.begin(),s1.end());
            st.insert(s1+s2);
            st.insert(s2+s1);
            reverse(s2.begin(),s2.end());
            st.insert(s1+s2);
            st.insert(s2+s1);
            reverse(s1.begin(),s1.end());
            st.insert(s1+s2);
            st.insert(s2+s1);
        }
        cout<<st.size()<<endl;
    }
    return 0;
}


Measured memory_bytes: 3220
def fact(n):
    x = 1
    for i in range(1, n + 1):
        x *= i
    return x


def nCr(n, r):
    return fact(n) // (fact(n - r) * fact(r))


def solve(N, K):
    if N < int("1" * K):
        return 0
    digits = [int(c) for c in str(N)]
    places = len(digits)
    count = 0
    for i in range(K - 1, places):
        # first digit then choose K-1 more places each 1-9
        firstChoice = 9
        if i == places - 1:
            # handle digits[0] case separate
            firstChoice = digits[0] - 1
        count += firstChoice * (9 ** (K - 1)) * nCr(i, K - 1)
    # digits[0] case
    if K == 1:
        count += 1
    else:
        count += solve(int("".join(map(str, digits[1:]))), K - 1)
    return count


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

print(solve(N, K))


Measured memory_bytes: 3064
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

map<string,LL>m;
string t;



int main()
{
    NO_TLE
    int n;
    cin>>n;
    LL ans=0;
    rep(i,n)
    {
        cin>>t;
        sort(t.begin(),t.end());
        m[t]++;
    }
    for(map<string,LL>::iterator i=m.begin();i!=m.end();++i)
    {
        LL tmp=i->second;
        //int f=1;
        if(tmp%2==0)ans+=(tmp/2)*(tmp-1);
        else ans+=((tmp-1)/2)*tmp;
    }
        cout<<ans<<endl;
    return 0;
}







































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

ll INF = 1e18;
ll MOD = 1e9+7;



int main() {
    ll N; cin >> N;
    map<string, ll> M;
    for(ll i = 0; i < N; i++){
        string S; cin >> S;
        sort(S.begin(), S.end());
        M[S]++;
    }
    ll ans = 0;
    for(auto m : M){
        if(m.second == 1) continue;
        else ans += (m.second*(m.second-1))/2;
    }
    cout << ans << endl;
}

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

#define ST_ARR_LEN(array) (sizeof(array)/sizeof(*array))
#define MOD 1000000007

using namespace std;

using ll = long long;
const ll MAX = LLONG_MAX;
const ll MIN = LLONG_MIN;

typedef stack<ll> llStack;
typedef queue<ll> llQueue;
typedef vector<ll> llVector;
typedef list<ll> llList;

typedef struct S{
  int a;
  int b;
} Object;

int main(){
  ll A, B, N;
  cin >> A >> B >> N;
  
  ll x;
  if(B == 1){
    x = 1;
  }else{
    x = B-1;
    if(B-1 > N){
      x = N;
    }
  } 
  ll ans = (A*x)/B-A*(x/B);
  
  cout << ans << endl;
}

Measured memory_bytes: 3624
lists = list(input())


flag = False

for i ,list in enumerate(lists):
    if (i + 1) % 2 == 1:
        if list == "R" or list == "U" or list == "D":
            flag = True
        else:
            flag = False
            break

    if (i + 1) % 2 == 0:
        if list ==  "L" or list == "U" or list == "D":
            flag = True
        else:
            flag = False
            break

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
// header {{{
// header {{{
using namespace std;
#include <bits/stdc++.h>
 
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
 
#define ASSERT(expr...) assert((expr))
 
using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
 
using f32 = float;
using f64 = double;
// }}}
 
constexpr i64 INF = 1'010'000'000'000'000'017LL;
 
constexpr i64 MOD = 1'000'000'007LL;
 
constexpr f64 EPS = 1e-12;
 
constexpr f64 PI = 3.14159265358979323846;

#define M5 100007
#define M9 1000000000

 
// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
 
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define ll long long int
#define VI vector <int>
template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
 
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
 
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
 
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
// }}}
 
// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
 
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}
 
//--------------------------------------------------------------------
 
bool isOK(int mid, double key){
 
    if((double)mid*mid > key) {
             return true;
     } else {
              return false;
     }
}

 int binary_search(double key) {
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = 2000000000;
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;

        if (isOK(mid, key)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}


bool isKaibun(string st){
    bool ans = true;
    int n = st.length();
    REP(i,n/2){
        if(st[i] != st[n-i-1]){
            return false;
        }
    }
    return true;
}

int toInt(char a){
    return a-'0';
}

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

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}

void solve() {
    int K;
    cin >> K;
    ll ans = 0;
    FOR(i,1,K+1){
        FOR(j,1,K+1){
                FOR(k,1,K+1){
                    ans += gcd(k,gcd(i, j));
                }
        }
    }
    cout << ans;
}



signed main() {
 
    solve();
 
    return 0;
}


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

using namespace std;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef long long ll;
typedef long double ld;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

const int N = 2e5;
ll pre[N+5];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n, d, a;
    cin >> n >> d >> a;
    vector<pair<ll, ll>> v(n);

    for(auto &z : v)
        cin >> z.fi >> z.se;

    sort(all(v));

    ll ans = 0LL;

    for(int i = 0, j = 0; i < n; ++i)
    {
        while(j < n && v[j].fi<=v[i].fi+2*d)
            ++j;
        ll treba = max((v[i].se-pre[i]*a+a-1)/a, 0LL);
        ans += treba;
        pre[i] += treba;
        pre[j] -= treba;
        pre[i+1] += pre[i];
    }

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


Measured memory_bytes: 7976
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
  static long startTime = System.currentTimeMillis();
  static Scanner sc = new Scanner(System.in);
  static ArrayList<ArrayList<Integer>> nei = new ArrayList<>();
  static int N;
  static int[] parent, ord, n2i, dp;

  public static void main(String[] args) {
    N = sc.nextInt();
    parent = new int[N];
    ord = new int[N];
    n2i = new int[N];
    dp = new int[N];
    for (int i = 0; i < N; i++) {
      nei.add(new ArrayList<>());
    }
    for (int i = 0; i < N - 1; i++) {
      int A = Integer.parseInt(sc.next());
      int B = Integer.parseInt(sc.next());
      nei.get(A).add(B);
      nei.get(B).add(A);
    }
    ArrayList<Integer> cand = new ArrayList<>();
    ArrayList<Integer> other = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      if (nei.get(i).size() == 1) {
        cand.add(i);
      } else {
        other.add(i);
      }
    }
    int ans = N;
    Collections.shuffle(cand);
    Collections.shuffle(other);
    for (int i = 0; i < cand.size(); i++) {
      if (System.currentTimeMillis() - startTime > 1800) break;
      int start = cand.get(i);
      ans = Math.min(ans, count(start));
    }
    for (int i = 0; i < other.size(); i++) {
      if (System.currentTimeMillis() - startTime > 1800) break;
      int start = other.get(i);
      ans = Math.min(ans, count(start));
    }
    System.out.println(ans);
  }

  static int count(int s) {
    ord[0] = s;
    n2i[s] = 0;
    parent[0] = -1;
    int pos = 1;
    for (int i = 0; i < N; i++) {
      for (int n : nei.get(ord[i])) {
        if (n != parent[i]) {
          ord[pos] = n;
          n2i[n] = pos;
          parent[pos] = ord[i];
          ++pos;
        }
      }
    }
    Arrays.fill(dp, 0);
    int ret = 1;
    for (int i = N - 1; i >= 0; i--) {
      int cur = ord[i];
      dp[i] = 0;
      int ec = 0;
      for (int n : nei.get(cur)) {
        if (n == parent[i]) continue;
        if (dp[n2i[n]] == 0) {
          ++ec;
        } else {
          dp[i] += dp[n2i[n]];
        }
      }
      if (ec > 1) dp[i] += ec - 1;
    }
    return dp[0] + 1;
  }

}


Measured memory_bytes: 222644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int k = sc.nextInt();
        String str = sc.next();
        int n = str.length();

        if (n <= k) {
            System.out.println(str);
        } else {
            System.out.println(str.substring(0, k) + "...");
        }

        System.exit(0);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


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

int main()
{
  int N,S[1000],SS[1000],SSS[1000],P[1000001],OP[1000001],a=0;
  S[0]=0;P[0]=0;OP[0]=0;
  for(int i=1;i<1000001;i++){
    OP[i]=P[i]=10000001;
  }
  for(int i=1;i<300;i++){
    S[i]=S[i-1]+i;
  }
  SS[0]=0;
  for(int i=1;i<300;i++){
    SS[i]=SS[i-1]+S[i];
    if(SS[i]%2==1)SSS[a++]=SS[i];
  }
  for(int i=0;i<a;i++){
    for(int j=SSS[i];j<1000001;j++){
      OP[j]=min(OP[j],OP[j-SSS[i]]+1);
    }
  }
  for(int i=1;i<300;i++){
    for(int j=SS[i];j<1000001;j++){
      P[j]=min(P[j],P[j-SS[i]]+1);
    }
  }
  while(1){
    cin>>N;
    if(N==0)break;
    cout<<P[N]<<" "<<OP[N]<<endl;
  }
  return 0;
}

Measured memory_bytes: 8984
#include<iostream>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<queue>


int main(){
	int n, m;
	long long mod= 1000000007;
	std::cin>>n>>m;

	std::vector<long long> dpList(n+1, 0);
	std::vector<bool> isBroken(n+1, false);
	std::vector<int> aList(m);

	for(int i=0; i<m; i++)
		std::cin>>aList[i];

	for(int i=0; i<m; i++)
		isBroken[aList[i]]= true;

	dpList[0]=1;

	for(int i=0; i<n; i++){
		if(!isBroken[i+1])
			dpList[i+1]= (dpList[i]+dpList[i+1])%mod;

		if(i+1<n && !isBroken[i+2])
			dpList[i+2]= (dpList[i]+dpList[i+2])%mod;

	}

	std::cout<<dpList[n]<<std::endl;


	return 0;
	
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();
    ll a, b, k; cin >> a >> b >> k;
    rep(i, k){
        if(i%2 == 0){
            // Takahashi
            if(a%2 == 1) a--;
            a /= 2;
            b += a;
        }
        else{
            // Aoki
            if(b%2 == 1) b--;
            b /= 2;
            a += b;
        }
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 3668
s = input()

arr = ['A', 'T', 'G', 'C']

def findLength(index):
    length = 0
    for c in s[index:]:
        if c in arr:
            length +=1
        else:
            break
    return length

max_length = 0
for i in range(0, len(s)):
    L = findLength(i)
    max_length = max(max_length, L)
    

print(max_length)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 200001
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n;
string s, t;

signed main(){
    cin >> s >> t;
    int cnt = 0;
    for(int i=0; i<3; i++){
        if(s[i] == t[i]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	long long int x;
	cin >> x;
	if (!(x % 11))cout << x / 11 * 2 << endl;
	else if (x % 11 > 6) cout << ((x + 10 )/ 11) * 2 << endl;
	else cout << (x / 11) * 2 + 1 << endl;
	return 0;
}


Measured memory_bytes: 256
//AtCoder1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream> 
#include <algorithm>
#include <math.h> 
#include <vector>
#include <string>
#include <iomanip>
using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if (s == u) {
        cout << a - 1 << " " << b << endl;
    }
    else { cout << a << " " << b - 1 << endl; }
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i,k,n) for (ll i = k; i < n; ++i)
#define inputar(a,n) ll a[n];rep(i,0,n)cin>>a[i]
#define PI 3.14159265
const int MOD=1e9+7;
const int N=2e5+10;


#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a)  (a).begin(),(a).end()


#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;

bool isPrime(int n) 
{ 
    if (n <= 1) 
        return false; 
    for (int i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
} 
int binomialCoeff(int n, int k)  
{
    if (k == 0 || k == n)  
        return 1;  

    return binomialCoeff(n - 1, k - 1) +  
                binomialCoeff(n - 1, k);  
}  
long long power(ll a, ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}

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

vector<int>v[N];
ll sum[N];

void dfs(int n,int vis)
{
    for(int i=0;i<v[n].size();i++)
    {
        if(v[n][i]!=vis)
        {
            sum[v[n][i]]+=sum[n];
            dfs(v[n][i],n);
        }
    }
}


int main()
{
    IOS;
    int n;
    cin>>n;
    string s[n];
    map<string,int>m;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        sort(s[i].begin(),s[i].end());
        m[s[i]]++;
    }
    ll c=0;
    for(auto i=m.begin();i!=m.end();i++)
    {
        ll x=i->second;
        c+=(x*(x-1))/2;
    }
    cout<<c<<endl;
    


}

Measured memory_bytes: 21376
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>G[N];
int n,dp[N],f;
void dfs(int i,int p)
{
    int F=0;
    for(auto j:G[i])
    {
        if(j==p)continue;
        dfs(j,i);
        dp[i]+=dp[j];
        if(!dp[j])
        {
            if(!F)F=1;
            else dp[i]++;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v; i<n; i++)
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    f=-1;
    for(int i=0; i<n; i++)
        if(G[i].size()>2)
        {
            f=i;
            break;
        }
    if(f==-1)printf("1\n");
    else dfs(f,-1),printf("%d\n",dp[f]);
    return 0;
}


Measured memory_bytes: 10368
N, W = map(int, input().split())

w, v = [0] * N, [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j - w[i] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])            


Measured memory_bytes: 120300
#include<bits/stdc++.h>
using namespace std;
#define fifo ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define ll long long int
#define w(t) ll t; cin>>t; while(t--)
#define pb push_back
#define vll vector<long long int>
#define vi vector<int>
#define mp make_pair
/*
ll GCD(ll a,ll b)
{
	if(b==0)
	return a;
	else
	return GCD(b,a%b);
}


ll x,y,d;       //d is gcd x and y are coefficients
void exten_euclid(ll a,ll b)
{	ll temp;
	if(b==0)
	{
		d=a;
		x=1;
		y=0;	
	}
	else
	{
		exten_euclid(b,a%b);
		temp=x;
		x=y;
		y=temp-(a/b)*y;	
	}
return;
}

ll fastModExp(ll a,ll b)
{
	ll res=1;
	while(b>0)
	{
		if(b&1)
		res=(res*a)%m;
	a=(a*a)%m;
	b=b>>1;	
	}
return res;
}


bool isPrime(ll n) {
	if(n==1)
      return false;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;               //O(root(N))
        }
    }
    return true;
}

vector<ll> factorize(ll n) {
    vector<ll> res;
    for (ll i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1) {
        res.push_back(n);
    }
    return res;
}

/*************FACTORIZE IN 0(LOG(N)) PROVIDED N IS INTEGER**************

int minPrime[100000];

void modified_sieve(int n){
for (int i = 2; i * i <= n; ++i) {
    if (minPrime[i] == 0) {         //If i is prime
        for (int j = i * i; j <= n; j += i) {
            if (minPrime[j] == 0) {
                minPrime[j] = i;
            }
        }
    }
}
for (int i = 2; i <= n; ++i) {
    if (minPrime[i] == 0) {
        minPrime[i] = i;
    }
}
}

vector<int> factorize(int n) {
    vector<int> res;
    while (n != 1) {
        res.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    return res;
}

/*************************************************
void sieve(int N) {
        bool isPrime[N+1];
        for(int i = 0; i <= N;++i) {
            isPrime[i] = true;
        }
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i * i <= N; ++i) {
             if(isPrime[i] == true) {                    
                 for(int j = i * i; j <= N ;j += i)
                     isPrime[j] = false;
            }
        }
    }
*/

ll binomialCoeff(ll n, ll k)  
{  
     ll res = 1; 
	if(n<k)
	return 0; 
  
    // Since C(n, k) = C(n, n-k)  
    if ( k > n - k )  
        k = n - k;  
  
    // Calculate value of  
    // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]  
    for (ll i = 0; i < k; ++i)  
    {  
        res *= (n - i);  
        res /= (i + 1);  
    }  
  
    return res;  
}  




map<ll ,ll> mpx;
int main()
{
fifo;
ll n,x;
vll v;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
mpx[x]+=1;
v.pb(x);
}
ll count =0;
map<ll,ll> :: iterator itr;
for( itr=mpx.begin();itr!=mpx.end();itr++){
count+=binomialCoeff(itr->second,2);
}
//cout<<count;
for(int i=0;i<n;i++){
ll r=mpx[v[i]];
cout<<count-binomialCoeff(r,2)+binomialCoeff(r-1,2)<<endl;
}


return 0;
}

Measured memory_bytes: 11120
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int i=0;
    int ans = 0;
    int ans2 =0;
    for (i = 0; i < 1100; i++) {
    	ans = (int)(i*0.08);
    	ans2=(int)(i*0.10);
    	if (ans ==a && ans2 == b) {
    		break;
    	}
    }
    if (i >=1100){
    	ans=-1;
    } else{
    	ans=i;
    }
    System.out.println(ans);
  }
}






Measured memory_bytes: 22868
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
int main() {
	cin >> n;
	if (n % 2 == 1) {
		cout << 0 << endl;
	}
	else {
		a = n/10;
		n = n/10;
		while (n > 0) {
			a += n/5;
			n = n / 5;
		}
		cout << a << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define MAX 20
#define INFTY (1<<21)

class Node{
    public:
    int P;
    vector<int> C;
    Node(){
	P = -1;
	C.clear();
    }
};

int N, G[MAX][MAX], total;
Node node[MAX];
bool visited[MAX];

void dfs(int u, int p){
    visited[u] = true;
    node[u].P = p;
    rep(v, N){
	if ( G[u][v] == INFTY || visited[v]) continue;
	node[u].C.push_back(v);
	dfs(v, u);
    }
}

void parse(int u, int cost){
    visited[u] = true;
    if ( node[u].C.size() == 0 ) return;

    for ( int i = 0; i < node[u].C.size(); i++ ){
	int v = node[u].C[i];
	if ( !visited[v] ) parse(v, G[u][v]);
    }
    total += cost*2;
}

int getCost(){
    rep(i, N) visited[i] = false;
    int cur = 0;
    total = 0;
    while( cur != -1 ){
	parse(cur, 0);
	if ( node[cur].P != -1 ) total += G[cur][node[cur].P];
	cur = node[cur].P;
    }
    return total;
}

int compute(){
    int minc = INFTY;
    for ( int s = 0; s < N; s++ ){
	rep(i, N) { visited[i] = false; node[i] = Node(); }
	dfs(s, -1);
	minc = min(minc, getCost());
    }
    return minc;
}

main(){
    int s, t, c;
    while( cin >> N && N ){
	rep(i, N) rep(j, N) G[i][j] = INFTY;
	rep(i, N-1){
	    cin >> s >> t >> c;
	    s--; t--;
	    G[s][t] = G[t][s] = c;
	}
	cout << compute() << endl;
    }
}

Measured memory_bytes: 0
import sys
from bisect import bisect_left, bisect_right
input = lambda: sys.stdin.readline()
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp1, dp2 = [0] * n, [0] * n
dp1[-1], dp2[-1] = 1, 1

for i in range(n-1)[::-1]:
    dp1[i] = dp1[i+1] + dp2[i+1] % MOD
    dp2[i] = dp1[s.get(i)]

print((dp1[0] + dp2[0]) % MOD)


Measured memory_bytes: 129212
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
#include <locale>
#include <cmath>
#include <iomanip>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    while(n != 0) {
        vector<int> data(n);
        for(int i = 0; i < n; i++) {
            cin >> data[i];
        }
        auto ave = accumulate(data.begin(), data.end(), 0.0) / data.size();
        double a = 0;
        for(int i = 0; i < n; i++) {
            a +=pow((data[i] - ave),2);
        }
        auto var = a / data.size();
        auto sd = sqrt(var);
        // cout << a << endl;
        // cout << ave << endl;
        cout << setprecision(10) << sd << endl;
        cin >> n;
    }
    return 0;
}


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

#define ll long long
#define debug(x) cerr << "\n" \
                      << #x << ": " << x << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define int long long
#define INF 1e9
#define pii pair<int, int>
#define pt(xx) cout << "\n" \
                    << xx << "\n"
#define debugv(x, n)               \
    cout << "\n"                   \
         << #x << ": ";            \
    rep(i, n) cout << x[i] << " "; \
    cout << endl
#define debug2d(x, m, n)            \
    cout << "\n"                    \
         << #x << " is: \n";        \
    for (int i = 0; i < m; ++i)     \
    {                               \
        for (int j = 0; j < n; ++j) \
        {                           \
            cout << x[i][j] << " "; \
        }                           \
        cout << endl;               \
    }
#define nl cout << endl

#define MOD 1000000007

int N, K,L;
int ans;

int A[100001];
// 10^12 < (2^10)^4
int dp[43][2] = {}; // dp[上からi桁][smaller(flag)];
const int maxd = 41;


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

    cin>>N>>L;

    vector<int> app(N);
    rep(i,N){
        app[i] = L+i;
    }

    int tmpsum = 0;
    int ans = INF;
    int allsum = 0;
    int ww = INF;
    rep(i,N){allsum += app[i];}
    rep(i,N){
        tmpsum = 0;
        rep(j,N){
            if (i != j) tmpsum += app[j];
        }
        int diff;
        if (tmpsum > allsum) diff = tmpsum - allsum;
        else diff = allsum - tmpsum;

        if (ww > abs(diff)) {
            ans = tmpsum;
            ww = abs(diff);
        }
    }

    cout<<ans<<endl;

    


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int w,h,n,x,y,a[N],b[N],c[N],d[N];
char s1[N],s2[N];
bool solve(int l,int r,int x,char u,char v)
{
	for (int i=1;i<=n;i++)
	{
		if (s1[i]==u) a[i]=-1;
		else if (s1[i]==v) a[i]=1;
		else a[i]=0;
		if (s2[i]==u) b[i]=-1;
		else if (s2[i]==v) b[i]=1;
		else b[i]=0;
	}
	memset(c,0,sizeof(c));memset(d,0,sizeof(d));
	int cnt=0;
	for (int i=n;i>=1;i--)
	{
		c[i]=c[i+1];
		if (a[i]==1) c[i]++;
		if (b[i]==-1) c[i]--;
		c[i]=max(c[i],max(0,a[i]));
		d[i]=d[i+1];
		if (a[i]==-1) d[i]--;
		if (b[i]==1) d[i]++;
		d[i]=min(d[i],min(0,a[i]));
	}
	int y=x;
	for (int i=1;i<=n;i++)
	{
		if (a[i]<=0) y+=a[i];
		if (y<l) return 1;
		if (b[i]>=0&&y+b[i]+c[i+1]<=r) y+=b[i];
	}
	y=x;
	for (int i=1;i<=n;i++)
	{
		if (a[i]>=0) y+=a[i];
		if (y>r) return 1;
		if (b[i]<=0&&y+b[i]+d[i+1]>=l) y+=b[i];
	}
	return 0;
}
signed main()
{
	h=read(),w=read(),n=read();
	x=read(),y=read();
	scanf("%s%s",s1+1,s2+1);
	if (solve(1,h,x,'U','D')||solve(1,w,y,'L','R')) cout<<"NO";
	else cout<<"YES";
	return 0;
	//NOTICE LONG LONG!!!!!
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                              \
  ifstream in("atcoder-problems/agc012_a.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;
  N *= 3;

  vector<ll> c(N);
  rep(i, N) { cin >> c[i]; }
  sort(c.begin(), c.end());

  ll ans = 0;
  ll cnt = 0;
  while (cnt < N/3) {
    c.pop_back();
    ans += c.back();
    c.pop_back();
    cnt++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#define debug(x...) cout << #x << " = "; _print(x)
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
#define rep(i,a,b) for (ll i = (a); i < (b); ++i)
#define per(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL) 
const int mod = 2019, mxn = 2001;

int solve(){
	string s;
	cin>> s;
	int n = s.size();
	vi cnt(2019, 0);
	int suff = 0, pow10 = 1;
	cnt[suff]++;
	ll ans = 0;
	per(i, 0, n){
		int digit = s[i] - '0';
		suff = suff + (digit * pow10)%mod;
		suff %= mod;
		ans += cnt[suff];
		cnt[suff]++;
		pow10 *= 10;
		pow10 %= mod;
	}	
	cout<< ans<< "\n";
	return 0;
}
 
int main()
{
    fast;
    int t = 1;
    //cin>> t;
    while(t--){  
        solve();
    }
    return 0;
}
//v.clear(), vis.clear(); vis.resize(n + 1, 0), v.resize(n + 1);
 
/*  inv[1] = 1; // inv is ll
    for(int i=2; i<=mxn; ++i)
        inv[i]=mod-mod/i*inv[mod%i]%mod;*/



Measured memory_bytes: 3748
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  if 2 <= i - v <= 100000001:
    c[i - v].append(i)
c = dict(c)

ans = 0
for v, L in b.items():
  for j in L:
    if v in c:
      ans += len(c[v])
print(ans)

Measured memory_bytes: 72196
[H,W] = list(map(int,input().split()))

a = []
for i in range(H):
    a.append(list(input()))

# print(*a, sep='\n')

line = []
colu = []
for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            line.append(i)
            colu.append(j)
# print('line:', line)
# print('culu:', colu)

ans=[]
for i in range(H):
    dammy=[]
    for j in range(W):
        if (i in line) and (j in colu):
            dammy.append(a[i][j])
    if dammy!=[]:
        ans.append(dammy)

for i in range(len(ans)):
    print(''.join(ans[i]))
#print(*ans)


Measured memory_bytes: 68148
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<map>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n;
map<ll,int> a;
queue<pii> q;
set<int> l[100010];
int f[100010];
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
ll getid(int x,int y)
{
	if(x>y)
		swap(x,y);
	return ll(x)*n+y;
}
void link(int x,int y)
{
	l[x].insert(y);
	l[y].insert(x);
	ll v=getid(x,y);
	a[v]++;
	if(a[v]==3)
	{
		printf("NO\n");
		exit(0);
	}
	if(a[v]==2)
		q.push(pii(x,y));
}
int main()
{
	scanf("%d",&n);
	int i,x,y;
	for(i=1;i<=2*n-2;i++)
	{
		scanf("%d%d",&x,&y);
		link(x,y);
	}
	for(i=1;i<=n;i++)
		f[i]=i;
	for(i=1;i<n;i++)
	{
		while(1)
		{
			if(q.empty())
			{
				printf("NO\n");
				return 0;
			}
			x=q.front().first;
			y=q.front().second;
			x=find(x);
			y=find(y);
			q.pop();
			if(x!=y)
				break;
		}
		if(l[x].size()>l[y].size())
			swap(x,y);
		f[x]=y;
		a.erase(getid(x,y));
		l[y].erase(x);
		for(auto v:l[x])
		{
			v=find(v);
			if(v==y)
				continue;
			a.erase(getid(x,v));
			link(v,y);
			l[v].erase(x);
			l[x].erase(v);
		}
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 38656
def check(s):
    if s[0] != 'A':
        return False
    c = s.find('C')
    rc = s.find('C')
    if c != rc:
        return False
    if c < 2 or len(s)-1 <= c:
        return False
    return ''.join(sorted(s)[2:]).islower()

print(['WA','AC'][check(input())])


Measured memory_bytes: 3064
# 解説AC
N,x = map(int, input().split())

if x == 1 or x == 2 * N - 1:
    print("No")
else:
    print("Yes")

    if N == 2:
        print(*range(1, 2 * N), sep="\n")
    else:
        if x == 2:
            not_use = list(range(5, 2*N))
            ans = not_use[::2]
            ans += [3,2,1,4]
            ans += not_use[1::2]
        else:
            not_use = list(range(1, x-2)) + list(range(x+2, 2*N))
            ans = not_use[::2]
            ans += [x-1,x,x+1,x-2]
            ans += not_use[1::2]
        print(*ans, sep="\n")

Measured memory_bytes: 17320
n,m,q=map(int,input().split())
Q=[list(map(int,input().split()))for i in range(q)]
from itertools import combinations_with_replacement

ans=0
for c in combinations_with_replacement(range(n),m-1):
    A=[0]*n
    for i in c:
        A[i]+=1
    for i in range(1,n):
        A[i]+=A[i-1]
    score=0
    #print(A,c)
    for a,b,c,d in Q:
        if A[b-1]-A[a-1]==c:
            score+=d
    ans=max(ans,score)
print(ans)

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

using namespace std;

int main() {
     long long N;
     cin >> N;
     long long A[N];
     for (int i = 0; i < N; ++i)  cin >> A[i];
     
     int state = 0;
     long long res = 1;
     
     for (int i = 0; i < N-1; ++i) {
         if (state == 0 && A[i] < A[i+1]) state = 1;
         else if (state == 0 && A[i] > A[i+1]) state = -1;
         else if (state == 1 && A[i] > A[i+1]) {
             state = 0;
             ++res;
         }
         else if (state == -1 && A[i] < A[i+1]) {
             state = 0;
             ++res;
         }
     }
     
     cout << res << endl;
}

Measured memory_bytes: 1024
from collections import Counter

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)


Measured memory_bytes: 35612
s=input()
n=len(s)
a=int(n)
b=int((n-1)/2)
c=int((n+3)/2)

for i in range (a//2):
  if s[i]!=s[a-1-i]:
    print ('No')
    exit()
    
for j in range (b//2):
  if s[i]!=s[b-1-i]:
    print('No')
    exit()
    
for k in range (c-1,a//2):
  if s[i]!=s[c-1-i]:
    print('No')
    exit()
    
print('Yes')

Measured memory_bytes: 3064
using System;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            var _ = Console.ReadLine().Split();
            var n = long.Parse(_[0]);
            var y = long.Parse(_[1]);

            var flag = Solve(n, y);
            if(!flag){
                Console.WriteLine("-1 -1 -1");
            }
        }

        static bool Solve(long n, long y){
            for(var i = 0; i <= n; i++){
                for(var j = 0; j <= n - i; j++){
                    var k = n - i - j;

                    var total = (10000 * i) + (5000 * j) + (1000 * k);
                    if(total == y){
                        Console.WriteLine(string.Format("{0} {1} {2}", i, j, k));
                        return true;
                    }
                }
            }
            return false;
        }
    }
}


Measured memory_bytes: 13140