akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

char s[200010];
int n;

vector<int> where[26];
vector<int> nn[26];
int nnn;

char des[200010];
int ni[200010];

int fen[200010];

int main()
{
	scanf("%s", s); n=strlen(s);
	for(int i=0; i<n; ++i) where[s[i]-'a'].pb(i);
	if(count_if(where,where+26,[](auto& v){return v.size()%2;})>=2){ puts("-1"); return 0; }
	int dn=0;
	for(int i=0; i<n; ++i){
		int v=s[i]-'a', p=lower_bound(all(where[v]), i)-where[v].begin();
		if(p<int(where[v].size())/2) des[dn++] = s[i];
	}
	for(int i=0; i<n/2; ++i) des[n-1-i]=des[i];
	if(n%2==1){
		for(int i=0; i<26; ++i) if(where[i].size()&1){
			des[n/2]='a'+i;
		}
	}
	for(int i=0; i<n; ++i) nn[s[i]-'a'].pb(i);
	int ci[26]; fill(ci, ci+26, 0);
	for(int i=0; i<n; ++i){
		int v=des[i]-'a';
		ni[i]=1+nn[v][ci[v]++];
	}
	ll ans=0;
	for(int i=n-1; 0<=i; --i){
		int f=ni[i];
		while(f) ans+=fen[f], f&=(f-1);
		f=ni[i];
		while(f<=n) fen[f]++, f+=(f&(-f));
	}
	printf("%lld\n", ans);
	return 0;
}


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

#define int long long

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

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

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

const int INF = 1e16;
const int MOD = 1e9+7;

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


signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    while(true)
    {
        int n, x; cin >> n >> x;
        if(n == 0 && x == 0) break;
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = i+1; j <= n; j++)
            {
                if(j < x-(i+j) && x-(i+j) <= n) ans++;
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3156
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner entrada = new Scanner(System.in);
        char letter= entrada.next().charAt(0);
        if (Character.isUpperCase(letter)){
            System.out.println("A");
        }else{
            System.out.println("a");
        }

    }
}

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

using namespace std;

#define INP "solve"
#define OUT "solve"

const int QQ = 3e5 + 10;
const int maxN = 3e5 + 100;
const int maxM = 3e5 + 10;
const long long oo = 1e18;
const int module = 1e9 + 7;
const long double du = 1e-9;

void doc() {
    freopen(INP ".inp","r",stdin);
    freopen(OUT ".out","w",stdout);
}

void solve() {
    int N;
    cin >> N;
    cout << (N - 1) / 2;
}
int main(int argc,char *argv[]) {
    //srand(time(nullptr));
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    ///doc();
    solve();
}


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

int main(){
    int n,q;
    cin>>n;
    vector<ll> a(n);
    ll ans=0;
    map<int,int> mp;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans+=a[i];
        if(mp.count(a[i])){
            mp[a[i]]++;
        }
        else{
            mp[a[i]]=1;
        }
    }
    cin>>q;
    vector<ll> b(q),c(q);
    for(int i=0;i<q;i++){
        cin>>b[i]>>c[i];
    }

    for(int i=0;i<q;i++){
        int k=mp[b[i]];
        ans+=k*(c[i]-b[i]);
        cout<<ans<<endl;
        mp.erase(b[i]);
        if(mp.count(c[i])){
            mp[c[i]]+=k;
        }
        else{
            mp[c[i]]=k;
        }
    }

}

Measured memory_bytes: 8532
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n,c;
    cin >> n >> c;
    VVI d(c, VI(c)), b(n, VI(n));
   // VVVI bb(3, VVI(n, VI(n)));
    REP(i,0,c) REP(j,0,c) cin >> d[i][j];
    REP(i,0,n) REP(j,0,n) {
        cin >> b[i][j];
        b[i][j] -= 1;
        //bb[(i%3)*3+j%3][i/3][j/3] = b[i][j];
    }
    int res[3][30] = {};
    REP(i,0,n) REP(j,0,n) {
        REP(k,0,c) {
            res[(i+j)%3][k] += d[b[i][j]][k];
        }
    }
    int ans = 1000 * 500 * 500;
    REP(i,0,c) REP(j,0,c) REP(k,0,c) {
        if (i == j || j == k || k == i) continue;
        int sum = res[0][i] + res[1][j] + res[2][k];
        ans = min(ans, sum);
    }
    cout << ans << endl;
}

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

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

#define M 1000001
#define L 14

char H[M][L]; /* Hash Table */
typedef long long ll;

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

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[])
{
	ll key = 0, i = 0, l = 0;
	key = getKey(str);
	while (1)
	{
		l = (h1(key) + i*h2(key)) % M;
		if (strcmp(H[l], str)==0)
		{
			return 1;
		}
		else if (strlen(H[l]) == 0)
		{
			return 0;
		}
		i++;
	}
}

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

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: 15448
M, D = map(int, input().split())

ans = 0
for d in range(1, D + 1):
    d_1 = d % 10
    d_10 = d // 10
    if d_1 < 2 or d_10 < 2:
        continue
    m = d_1 * d_10
    if m <= M:
        ans += 1
print(ans)


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

int main(void){
	int n;

	while(cin>>n && n){
		char f[n][n];
		int count[n][n];
		int ans = 0;

		for(int i=0;i<n;i++){
			cin>>f[i];
			for(int j=0;j<n;j++){
				count[i][j] = f[i][j]=='.' ? (ans=1) : 0;
			}
		}

		for(int i=1;i<n;i++){
			for(int j=1;j<n;j++){
				if(f[i][j] == '*') continue;
				int nc = min(count[i-1][j-1],min(count[i-1][j],count[i][j-1]))+1;
				count[i][j] = nc;
				ans = max(nc,ans);
			}
		}

		cout<<ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <limits>
#include <numeric>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a<=8 && b<=8)cout << "Yay!" << endl;
	else cout << ":(" << endl;

	return 0;
}

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

#define mkf(n,mod)  int *fact=(int *)malloc((n+1)*sizeof(int)); mfac((n),fact,(mod)) //enables to let x!=fact[x]
#define mkfiv(n,mod)  int *finv=(int *)malloc((n+1)*sizeof(int)); mfiv((n),finv,fact[n],(mod)) // 1/x! = finv[x]
#define ncr(n,r,mod) mncr((n),(r),(mod),fact,finv)

int mmul(int p,int q,int m){ //O(1)?
    ll lp=p,lq=q; return ((lp%m)*(lq%m))%m;}

int mpow(int x,int n,int m){ //O(logN)
    ll res=x,ans=1;
    while(n!=0){
        if(n%2==0){ res = mmul(res,res,m);n>>=1;
        }else{      ans = mmul(ans,res,m);--n;}}return ans;}

int mdiv(int p,int q,int m){ //O(logMOD)
    return mmul(p,mpow(q,m-2,m),m);}

void mfac(int x,int *f,int m){//O(n)
    *f=1; for(int i=1;i<=x;++i)f[i]=mmul(f[i-1],i,m);}

void mfiv(int x,int *f,int fx,int m){//O(n)
    f[x] = mdiv(1,fx,m); 
    for(int i=x;i>0;--i)f[i-1]=mmul(f[i],i,m);}

int mncr(int n,int r,int m,int* fac,int* fiv){//O(1)
    return mmul(fac[n],mmul(fiv[r],fiv[n-r],m),m);}


int main(){
    bool flag=false;
    ll ans=0,sum=0;

    int n,k;
    cin >>n>>k;
    mkf(n,MOD);
    mkfiv(n,MOD);

    vector<int> a(n);
    rep(i,n)cin>>a[i];
    sort(all(a));

    rep1(i,k-1,n){
        int add = mmul(a[i],ncr(i,k-1,MOD),MOD);
        ans = (ans+add)%MOD;

        //db(add);ln;
    }

    reverse(all(a));
    rep1(i,k-1,n){
        int dif = mmul(a[i],ncr(i,k-1,MOD),MOD);
        dif = MOD - dif;

        ans = (ans+dif)%MOD;
        //db(dif);ln;
    }


    //cout <<fixed<<setprecision(16)<< << endl;
    cout<<ans<<endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 1408
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
ans = a[0]
cnt = 0
j = 1
for i in range(2, n):
    if cnt < 2:
        ans += a[i-j-cnt]
        cnt += 1
    if cnt == 2:
        cnt = 0
        j += 1
print(ans)

Measured memory_bytes: 94220
/////////////////////////////////////////
///       Please Give Me AC!!!!!      ///
/////////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main() {
    ll Q, H, S, D;
    cin>> Q >> H >> S >> D;
    ll N;
    cin>> N;

    ll A = min({Q*4, H*2, S});
    cout<< min(A*N, D*(N/2) + A*(N%2)) << endl;
}

Measured memory_bytes: 3596
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication24
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int a = int.Parse(Console.ReadLine());
                if (a == 0)
                    break;
                int b = 0;
                for (int c = 0; c < a; c++)
                {
                    double[] d = Console.ReadLine().Split().Select(double.Parse).ToArray();
                    if (d[0] + d[1] + d[2] <= 60 && d[3] <= 2)
                        b += 600;
                    else if (d[0] + d[1] + d[2] <= 80 && d[3] <= 5)
                        b += 800;
                    else if (d[0] + d[1] + d[2] <= 100 && d[3] <= 10)
                        b += 1000;
                    else if (d[0] + d[1] + d[2] <= 120 && d[3] <= 15)
                        b += 1200;
                    else if (d[0] + d[1] + d[2] <= 140 && d[3] <= 20)
                        b += 1400;
                    else if (d[0] + d[1] + d[2] <= 160 && d[3] <= 25)
                        b += 1600;
                }
                Console.WriteLine(b);
            }
        }
    }
}

Measured memory_bytes: 9720
def main(istr, ostr):
  x, y = istr.readline().strip().split()
  a = int(x)
  b0, _, b1, b2 = y
  b0, b1, b2 = list(map(int, [b0, b1, b2]))

  c = a * (100 * b0 + 10 * b1 + b2)
  res = c // 100
  print(res, file=ostr)


if __name__ == "__main__":
  import sys

  main(sys.stdin, sys.stdout)


Measured memory_bytes: 9088
#include<iostream>
using namespace std;
#define df 0

int main(){
  if(df) printf("*debug mode*\n");
  int n,a,b; cin >> n >> a >> b;
  if(n>(long int)a*b || n<a+b-1){
    cout << "-1\n";
    return 0;
  }
  if(a==1){
    for(int i=n;i>0;i--){
      cout << i << (i!=1? " ":"\n");
    }
    return 0;
  }
  int q=(n-b)/(a-1), r=(n-b)%(a-1);
  for(int i=b;i>0;i--){
    cout << i << " ";
  }
  int i,j0=b;
  for(i=1;i<=r;i++){
    j0+=q+1;
    for(int j=0;j<q+1;j++){
      cout << j0-j << " ";
    }
  }
  for(;i<a;i++){
    j0+=q;
    for(int j=0;j<q;j++){
      cout << j0-j << " ";
    }
  }
  cout << "\n";
}

/// confirm df==0 ///


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

int main(){
    int n;
    cin>>n;
    vector<int>a(n),b(1000001,0);
    map<int,int>mp;
    rep(i,n){
        cin>>a[i];
        if(b[a[i]]==0){
            for(int j=a[i]; j<1000001; j+=a[i]){
                b[j]++;
            }
        }
        else{
            b[a[i]]=2;
        }
    }
    int ans=0;
    rep(i,n)if(b[a[i]]==1)ans++;
    cout<<ans<<endl;
}

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

using namespace std;

int main()
{
    string s;
    int count =0;
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]==s[i+1])
        {
            s[i+1]=(s[i]=='0')? '1' : '0';
            count++;
        }
    }
    cout << count << endl;
    return 0;
}



Measured memory_bytes: 512
s = input()
cnt = 0
li = [0]
for i in range(len(s)):
  if s[i] == "A" or s[i] == "C" or s[i] == "G"or s[i] == "T":
    cnt += 1
    if i == len(s)-1:
      li.append(cnt)
  else:
    li.append(cnt)
    cnt = 0
print(max(li))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

void solve()
{
    int k;
    string s;
    cin >> k >> s;

    s = s.length() <= k ? s : s.substr(0, k) + "...";
    cout << s << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Measured memory_bytes: 3576
#include <string>
#include <iostream>
using namespace std;
int main(){
  int N,M,A;
  cin >> N >> M;
  for(int i=0;i<M;i++){
    cin >> A;
    N=N-A;
  }
  if(N<0)
    cout << -1 <<endl;
  else
    cout << N <<endl;
}


Measured memory_bytes: 3636
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D: Insertion
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  int sum = 0, minsum = 0;
  for (int i = 0; i < n; i++) {
    sum += ((s[i] == '(') ? 1 : -1);
    if (minsum > sum) minsum = sum;
  }

  int k0 = -minsum;
  int k1 = sum + k0;

  for (int i = 0; i < k0; i++) putchar('(');
  for (int i = 0; i < n; i++) putchar(s[i]);
  for (int i = 0; i < k1; i++) putchar(')');
  putchar('\n');
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string.h>
#include <functional>

using namespace std;
typedef long long llong;

int gcd(int x, int y) {
	if (x < y) swap(x, y);
	if (y == 0) return x;
	return gcd(y, x % y);
}

int phi(int x) {
	int ret = 1;
	for (int i = 2; (llong)i * i <= x; ++i) {
		int cnt = 0;
		while (x % i == 0) x /= i, ret *= i, ++cnt;
		if (cnt) ret = ret / i * (i - 1);
	}
	if (x > 1) ret *= x - 1;
	return ret;
}

llong mul(llong a, llong b, llong m) {
	llong ret = 0ll;
	a %= m;
	while (b) {
		if ((b & 1ll) != 0ll) ret = (ret + a) % m;
		b >>= 1;
		a = (a << 1) % m;
	}
	return ret;
}

llong pow(llong a, llong p, llong m) {
	llong ret = 1ll;
	while (p) {
		if ((p & 1ll) != 0ll) ret = mul(ret, a, m);
		a = mul(a, a, m);
		p >>= 1;
	}
	return ret;
}

llong solve(int a, int m) {
	if (m == 1) return 50;
	int n = m, g;
	while ((g = gcd(a, n)) != 1) n /= g;
	if (n == 1) return m * (50 / m + 1);
	int p = phi(n);
	llong ret = solve(a, p);
	llong mod = (llong)m * p;
	ret = pow(a, ret, mod);
	while (ret < 50) ret += mod;
	return ret;
}

int main() {
	int T, a, m;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &a, &m);
		printf("%lld\n", solve(a, m));
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <ctime>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const ll INF = 10e16;
const int maxN = 5010;
const int maxM = 100010;
const int N = 5000; 
const int MOD = 1000000007;

ll a,b,c,k;
ll mx = 1e18;
int main()
{

	scanf("%lld %lld %lld %lld",&a,&b,&c,&k);
	ll x ;
	if(k%2 == 1)
	{
		x = b-a;
	}
	else
	{
		x = a-b;
	}
	if(x>mx)
	{
		printf("Unfair\n");
	}
	else
	{
		printf("%lld",x);
	}
	return 0;
}  

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define oo 10000
#define N 110
using namespace std;

struct node
{
	int x,y,p,q,dir;

	node (){}
	node (int a,int b,int c,int d,int e):x(a),y(b),p(c),q(d),dir(e){}
};

char dp[N][N][12][12][4];
queue<node>que;
char map[N][N];
int mx[4]={-1,0,1,0},my[4]={0,1,0,-1};
int n,m,a;

bool in_range(int x,int y) {return (x>=0&&x<n&&y>=0&&y<m);}

int main()
{
	int i,j,k,sx,sy,ex,ey,ans,tx,ty;
	node u,v;

	scanf("%d%d%d",&n,&m,&a);
	for (i=0;i<n;i++)
		scanf("%s",map[i]);
	for (i=0;i<n;i++)
		for (j=0;j<m;j++)
		{
			if (map[i][j]=='S') {sx=i;sy=j;}
			if (map[i][j]=='G') {ex=i;ey=j;}
		}


	tx=sx; ty=sy;
	tx+=mx[2]; ty+=my[2];
	if (!in_range(tx,ty)||map[sx][sy]=='#')
	{
		printf("-1\n");
		return 0;
	}

	ans=oo;
    while (in_range(tx,ty)&&map[tx][ty]!='#')
    {
        memset(dp,0,sizeof(dp));
        dp[tx][ty][0][0][2]=1;
        que.push(node(tx,ty,0,0,2));
        while (!que.empty())
        {
            u=que.front(); que.pop();
            if(u.x>=sx&& u.x <= tx && u.y == ty && u.dir == 0) continue;
            v=u;
            v.x+=mx[u.dir]; v.y+=my[u.dir];
            if (in_range(v.x,v.y)&&map[v.x][v.y]!='#')
            {
                if (dp[v.x][v.y][v.p][v.q][v.dir]==0)
                {
                    dp[v.x][v.y][v.p][v.q][v.dir]=1;
                    que.push(v);
                }
            }

            if (map[u.x][u.y]=='.')
            {
                v=u;
                v.dir=(v.dir+1)%4;
                if (u.dir%2==0)
                    v.q++;
                else
                    v.p++;
                v.x+=mx[v.dir]; v.y+=my[v.dir];
                if (v.q<=a&&v.p<=a&&in_range(v.x,v.y)&&map[v.x][v.y]!='#')
                {
                    if (dp[v.x][v.y][v.p][v.q][v.dir]==0)
                    {
                        dp[v.x][v.y][v.p][v.q][v.dir]=1;
                        que.push(v);
                    }
                }

                v=u;
                v.dir=(v.dir+3)%4;
                if (u.dir%2==0)
                    v.p++;
                else
                    v.q++;
                v.x+=mx[v.dir]; v.y+=my[v.dir];
                if (v.q<=a&&v.p<=a&&in_range(v.x,v.y)&&map[v.x][v.y]!='#')
                {
                    if (dp[v.x][v.y][v.p][v.q][v.dir]==0)
                    {
                        dp[v.x][v.y][v.p][v.q][v.dir]=1;
                        que.push(v);
                    }
                }
            }
        }

        for (i=0;i<=a;i++)
            for (j=0;j<=a;j++)
            for (k=0;k<4;k++)
                if (dp[ex][ey][i][j][k])
                {
                    if (k==0&&ey==sy&&ex>=sx&&ex<=tx) continue;
                    ans=min(ans,i+j);
                }

        tx+=mx[2]; ty+=my[2];
	}

	if (ans==oo)
		printf("-1\n");
	else
		printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 8004
use std::vec::Vec;
use std::cmp::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
  let s: Vec<char> = read::<String>().chars().collect();

  let mut b = true;

  for i in 0..3 {
    if s[i] == s[i+1] {
      b = false
    }
  }

  if b {
    println!("Good");
  } else {
    println!("Bad");
  }
}


Measured memory_bytes: 4352
# coding: utf-8
# Here your code !
def searchEmployeeSales(employeeId):
    for data in employeeSalesList:
        if data[0] == employeeId:
            return data
    
    newData = [employeeId, 0]
    employeeSalesList.append(newData)
    return newData

dataCount = int(input())
while dataCount > 0:
    employeeSalesList = []
    for _ in range(dataCount):
        dataList = input().split(" ")
        employeeId, price = dataList[0], int(dataList[1]) * int(dataList[2])
        employeeSales = searchEmployeeSales(employeeId)
        employeeSales[1] += price

    answerList = [data[0] for data in employeeSalesList if data[1] >= 1000000]
    if answerList:
        print("\n".join(map(str, answerList)))
    else:
        print("NA")

    dataCount = int(input())

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

using ll = long long;

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

    if(n == 0) {
        cout << 0 << endl;
        return 0;
    }

    string ans;
    while(n != 0) {
        ans += '0' + abs(n % 2);
        n = (n - abs(n % 2)) / -2;
    }
    reverse(begin(ans), end(ans));
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())

k15 = N // 15
m = N - (15 * k15)

k3 = m // 3
k5 = m // 5

def sigma(n):
  ans = (n * (n + 1)) / 2
  return ans

sum = (3 * sigma((5 * k15) + k3)) + (5 * sigma((3 * k15) + k5)) - (15 * sigma(k15))
an = sigma(N) - sum
print(int(an))

Measured memory_bytes: 9224
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] <= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) left = mid;
		else right = mid;
	}
	/* left は条件を満たす最大の値、right は条件を満たさない最小の値になっている */
	return left;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
double PI = 3.141592653589793238;
vector<vector<int>>G(100030);
int main() {
	int n;
	cin >> n;
	map<string, int>m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		m[s]++;
	}
	int ans = 0;
	for (auto iter = m.begin(); iter != m.end(); iter++) {
		ans++;
	}
	cout << ans;
}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  // ll N; cin >> N;
  // ll N, K; cin >> N >> K;
  ll x, y; cin >> x >> y;
  // ll a, b, c; cin >> a >> b >> c;
  vector<string> s(x); rep(i, x) cin >> s[i];

  rep(i, y + 2) cout << "#"; cout << "\n";
  rep(i, x) {
    cout << "#" << s[i] << "#\n";
  }
  rep(i, y + 2) cout << "#"; cout << "\n";
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3724
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;




//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)


int c[10][10];

void warshall() {
	REP(k, 10) {
		REP(i, 10) {
			REP(j, 10) {
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
			}
		}
	}
}



int main() {
	int h, w;
	cin >> h >> w;
	
	REP(i, 10) {
		REP(j, 10) {
			cin >> c[i][j];
		}
	}
	warshall();


	int sum = 0;
	REP(i, h*w) {
		int a;
		cin >> a;
		if (a != -1) {
			sum += c[a][1];
		}
	}
	cout << sum << endl;









	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int n, m, k;
	int x = 0;
	int ans = 0;
	scanf("%d %d %d", &n, &m, &k);
	if (k % n == 0 || k % m == 0)
	{
		ans = 1;
	}
	else
	{
		for (int i = 1; i <= (n / 2) + 1; i++)
		{
			if (ans == 1) break;
			for (int j = 1; j <= m; j++)
			{
				x = (m * i + n * j) - i * j * 2;
				if (x == k)
				{
					ans = 1;
					break;
				}
			}
		}
	}
	if (ans == 1)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
using namespace std;
int main() {
	string a;
	while (getline(cin,a)) {
		stack<double>s;
		a += " ";
		string h = "";
		double ans = 0;
		bool ans2 = false;
		for (int i = 0; i < a.length(); i++) {
			if (a[i] == ' ') {
				if (h == "-") {
					long double d = s.top();
					s.pop();
					long double e = s.top();
					s.pop();
					s.push(e - d);
				}
				else if (h == "+") {
					long double d = s.top();
					s.pop();
					long double e = s.top(); s.pop();
					s.push( d+e);
				}
				else if (h == "*") {
					long double d = s.top();
					s.pop();
					long double e = s.top(); s.pop();
					s.push(d*e);
				}
				else if (h == "/") {
					long double d = s.top();
					s.pop();
					long double e = s.top(); s.pop();
					s.push(e / d);
				}
				else {
					s.push(stoi(h));
				}
				h = "";
			}
			else h += a[i];
		}
		printf("%lf\n", s.top());
	}
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    string s; cin >> s;
    int n = s.length();

    bool ans = true;

    for (int i = 0; i < n; ++i) {
        if (s[i] != s[n-1-i]) {
            ans = false;
            break;
        }
    }

    for (int i = 0; i < (n-1)/2; ++i) {
        if (s[i] != s[(n-1)/2-1-i]) {
            ans = false;
            break;
        }
    }

    for (int i = (n+3)/2; i < n; ++i) {
        if (s[i] != s[n-1-i]) {
            ans = false;
            break;
        }
    }

    if (ans) {
        puts("Yes");
    } else {
        puts("No");
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
using namespace std;


using ll = long long int;

/// <summary>
/// GCDを計算します
/// </summary>
template <typename NumType>
NumType calcGCD(NumType a, NumType b) {
	if (a < b) {
		NumType tmp = a;
		a = b;
		b = tmp;
	}

	NumType r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

/// <summary>
/// 約数を数えます
/// </summary>
template <typename NumType>
NumType cntDivisor(const NumType& num) {
	NumType cnt = 0;
	for (NumType i = 1; i * i <= num; ++i) {
		if (num % i == 0) {
			cnt++;
			if (i * i != num) cnt++;
		}
	}

	return cnt;
}

/// <summary>
/// [beg, end)の範囲を，添え字indexでループするfor文に置換します
/// </summary>
#define FOR_RANGE(index, beg, end)     for (ll index = beg; index < end; ++index)

#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
#define BIT_FLAG_(i) (1 << i)



int main() {
	// 入出力を早くするための魔法の言葉
	cin.tie(0);ios::sync_with_stdio(false);


	string S;
	cin >> S;

	ll sum = 0, sum_tmp = 0;

	for (ll mask = 0; mask < (1 << (static_cast<ll>(S.size()) - 1)); ++mask) {
		sum_tmp = static_cast<ll>(S[0]) - static_cast<ll>('0');
		for (ll i = 0; i < static_cast<ll>(S.size()) - 1; ++i) {

			if (mask & (1 << i)) {
				sum += sum_tmp;
				sum_tmp = static_cast<ll>(S[i + 1]) 
					- static_cast<ll>('0');
			}
			else {
				sum_tmp = 10 * sum_tmp + 
					static_cast<ll>(S[i + 1]) 
					- static_cast<ll>('0');
			}
		}
		sum += sum_tmp;
	}

	cout << sum << endl;
}

Measured memory_bytes: 256
//hinagata.cpp
//作成日
//更新日
//目的
//手段
/*includes*/
#include <bits/stdc++.h>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPi(i,a,b) for(ll i=(a);i<(b);i++)
#define REPRi(i,a,b) for(ll i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()

int main(){
    int H,N;
    cin>>H>>N;
    vector<int> A(N);
    REP(i,N){
        cin>>A[i];
    }
    //inputend
    ll sum=accumulate(ALL(A),0);
    if(sum>=H){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <functional>

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n, n) {
        int S;
        cin >> S;
        n *= 2;
        vector<int> a(n);
        REP(i, 0, n) {
            cin >> a[i];
        }

        auto memo = make_v(S + 1, n, -1);
        function<int(int, int)> rec = [&](int rest, int turn) {
            if (memo[rest][turn] != -1) return memo[rest][turn];
            if (rest == 0) {
                return 1;
            }
            int ans = 1;
            REP(i, 1, a[turn] + 1) {
                if (rest < i) continue;
                ans *= rec(rest - i, (turn + 1) % n);
            }
            return memo[rest][turn] = (ans == 0);
        };
        cout << rec(S, 0) << endl;
    }
    return 0;
}



Measured memory_bytes: 4176
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  string s;cin>>s;
  int k;cin>>k;
  for(int i=0;i<s.size()-1;i++){
    int cost=('a'+26-s[i])%26;
    if(cost<=k){
      k-=cost;
      cout<<"a";
    }
    else cout<<s[i];
  }
  int a=s[s.size()-1]-'a'+k;
  a%=26;
  char z=a+'a';
  cout<<z<<endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  int ans = 0;
  rep (i, n) {
    cin >> v[i];
    int flag = 1;
    rep (j, i) {
      if (v[i] < v[j]) flag = 0;
    }
    if (flag == 1) ans++;
  }
  P(ans);
  return 0;

}

Measured memory_bytes: 256
// abc134c: Exception Handling
#include <stdio.h>

#define rep(i,s,e) for(int i=s;i<e;i++)
#define in(n) scanf("%d",n)
#define outi(d) printf("%d\n",d)

int main(){
  int n;in(&n);
  int ix=0,f=1,s=1;
  rep(i,0,n){
    int a;in(&a);
    if(a>f){ s=f; f=a; ix=i; }
    else if(a>s) s=a;
  }
  rep(i,0,n) outi(i==ix? s: f);
  return 0;
}

Measured memory_bytes: 1536
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
s=[0]*(n+1)
for i in a:
    s[i]=-1
s[0]=1
for i in range(1,n+1):
    if s[i]==-1:
        continue
    if s[i-1]==-1:
        s[i]=s[i]+s[i-2]
    elif s[i-2]==-1:
        s[i]+=s[i-1]
    else:
        s[i]=s[i]+s[i-1]+s[i-2]
if s[-1]==-1:
  print(0)
else:
  print(s[-1]%(10**9+7))

Measured memory_bytes: 470264
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal():
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N,E=map(int,input().split())
par=[i for i in range(N)]
rank=[0 for _ in range(N)]
Edge=[]
for i in range(E):
    s,t,w=map(int,input().split())
    Edge.append([s,t,w])
res=Kruskal()
print(res)


Measured memory_bytes: 26300
#include <iostream>
#include <map>

#define u unsigned
#define s short
#define ll long long
#define REP(i, a, b) for (auto i = (a); i < (b); i++)
#define REPR(i, a, b) for (auto i = (a-1); i >= (b); i--)

using namespace std;

int main()
{
    map<string, int> result;
    string verdicts[4] = {"AC", "WA", "TLE", "RE"};

    REP(i, 0, 4)
        result[verdicts[i]] = 0;

    int N; cin >> N;

    REP(i, 0, N)
    {
        string verdict; cin >> verdict;
        result[verdict] ++;
    }

    REP(i, 0, 4)
        cout << verdicts[i] << " x " << result[verdicts[i]] << "\n";

    return 0;
}

Measured memory_bytes: 3552
#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 int 		long long
#define vi 			vector<int>
#define vec(x) 		vector<x>
#define matrix 		vector<vector<int>>
#define pii 		pair<int,int>
#define repf(i,s,e)  for(int i=s;i<e;i++)
#define repb(i,e,s) for(int i=e;i>=s;i--)
#define MOD			1000000007
#define pb 			push_back
#define ff 			first
#define ss 			second
#define w(x)		int x; cin>>x; while(x--)
const int INF = 1e18;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k-1)  returns iterator to kth element starting from 0; Returns the kth smallest element
// order_of_key(k) returns count of elements strictly smaller than k;Returns the number of elements less than k
// erase,insert same as normal set


void solve() {
	string s;
	cin>>s;

	int dp[2019];memset(dp,0,sizeof(dp));// dp[i]-> number of numbers having the rem i

	int n=s.length(),ans=0;
	int ndp[2019];
	for(int i=0;i<n;i++){
		memset(ndp,0,sizeof(ndp));
		for(int j=0;j<2019;j++){
			ndp[(10*j+(s[i]-'0'))%2019]+=dp[j]; // from position j i can transit to state (10*j+nums[i])%2019;
		}
		ndp[s[i]-'0']++;
		ans+=ndp[0];
		memcpy(dp,ndp,sizeof(ndp));
	}

	cout<<ans<<endl;
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin),
		        freopen("output.txt", "w", stdout);
	}

	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
}

Measured memory_bytes: 3832
#include<bits/stdc++.h>
using namespace std;
int main(void){
int a,b,c,n=0;
cin>>a>>b>>c;
while(c!=n){
    if(b-a<0)
        break;
    else{
        b-=a;
        n+=1;
    }
}cout<<n<<endl;
return 0;}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n,x,y,i,j;
    cin>>n>>x>>y;
    vector<long long>ans(n),adj[n+2];
    for(i=1; i<=n; i++)
    {
        adj[i].push_back(i+1);
        adj[i+1].push_back(i);
    }
    adj[x].push_back(y);
    adj[y].push_back(x);
    for(i=1; i<=n; i++)
    {
        vector<int>dest(n+1,-1);
        queue<int>q;
        q.push(i);
        dest[i]=0;
        while(!q.empty())
        {
            int id=q.front();
            q.pop();
            for(auto p:adj[id])
            {
                if(dest[p]==-1)
                {
                    dest[p]=dest[id]+1;
                    q.push(p);
                }
            }
        }
        for(j=i+1; j<=n; j++)
            ans[dest[j]]++;
    }
    for(i=1; i<n; i++)
        cout<<ans[i]<<endl;
}




Measured memory_bytes: 384
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL n,a[3010],dp[3010][3010][2];

LL dfs(int lb,int ub,int t)
{
  if(ub<lb) return 0;
  if(dp[lb][ub][t]!=1e18) return dp[lb][ub][t];
  if(t==0) return dp[lb][ub][t]=max(dfs(lb+1,ub,1)+a[lb],dfs(lb,ub-1,1)+a[ub]);
  return dp[lb][ub][t]=min(dfs(lb+1,ub,0)-a[lb],dfs(lb,ub-1,0)-a[ub]);
}

int main()
{
  cin>>n;
  rep(i,n) cin>>a[i];
  rep(i,3005) rep(j,3005) rep(k,2) dp[i][j][k]=1e18;
  cout<<dfs(0,n-1,0)<<endl;
  return 0;
}

Measured memory_bytes: 141824
#include<bits/stdc++.h>
using namespace std;
int main ()         
{
  long long int n;cin>>n;
  long long int a[n],b[n],count=0;
  for (long long int i=0;i<n;i++) cin>>a[i];
  b[0]=a[0];
  for (long long int i=1;i<n;i++) {
      if (a[i]<b[i-1]) { b[i]=a[i];}
      else {b[i]=b[i-1];}
  }
   for (long long int i=0;i<n;i++) {
     //  cout<<b[i]<<endl;
       if (b[i]>=a[i]) count++;
   }
   cout<<count<<endl;




}

Measured memory_bytes: 3328
#include <stdio.h>

int main() {
    char day[100];
    scanf("%s", day);
    int y = 0, m = 0, d = 0;
    int ok = 1;
    for (int i = 0; i < 4; i++) y = y * 10 + (day[i] - '0');
    for (int i = 5; i < 7; i++) m = m * 10 + (day[i] - '0');
    for (int i = 8; i < 10; i++) d = d * 10 + (day[i] - '0');
    if (y != 2019) ok &= (y < 2019);
    else {
        if (m != 4) ok &= (m < 4);
        else if (d != 30) ok &= (d < 30);
    }

    printf("%s\n", (ok ? "Heisei" : "TBD"));
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for(int i = 0; i < 3000; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if (x == 0 && y == 0) {
                break;
            }
            if (x < y) {
                System.out.println(x + " " + y);
            } else {
                System.out.println(y + " " + x);
            }
        }
    }
}



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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }


void compute() {

}

int main() {
  string a,b;
  cin >> a >> b;
  int cnt = 0;
  rep(i,(int)a.size()) {
    if( a[i] == b[i] ) ++cnt;
  }
  cout << cnt << endl;
  compute();
  return 0;
}


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

using namespace std;

vector<unsigned long long> memo;

unsigned long long lucas(int n)
{
    if (n == 0) {
        memo[0] = 2;
    } else if (n == 1) {
        memo[1] = 1;
    } else if (memo[n] == 0) {
        memo[n] = lucas(n-1)+lucas(n-2);
    }

    return memo[n];
}

int main(int argc, char* argv[])
{
    int N; cin >> N;
    memo.resize(N+1, 0);
    
    cout << lucas(N) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
using namespace std;

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

  array<string, 100> str_array;
  int N, L;
  cin >> N >> L;
  for(int i = 0; i < N; i++) {
    cin >> str_array[i];
  }
  sort(str_array.begin(), str_array.begin()+N);
  string result = "";
  for(int i = 0; i < N; i++) {
    result += str_array[i];
  }
  cout << result;
}

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, y;
	cin >> n >> y;

	for (int i = n; i >= 0; i--) {
		for (int j = 0; j <= n - i; j++) {
			// for (int k = 0; k <= n - i - j; k++) {
				if (i + j + n - i - j == n && i * 10000 + j * 5000 + (n - i - j) * 1000 == y) {
					cout << i << " " << j << " " << (n - i - j) << "\n";
					return 0;
				}
			// }
		}
	}
	cout << "-1 -1 -1\n";
	return 0;
}

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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

int main() {
    string n;
    cin >> n;
    
    string rn = n;
    reverse(rn.begin(), rn.end());

    cout << (n == rn ? "Yes" : "No") << endl;

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  
  for (int i = 0;s.length() - 1 > i;i++) {
    if (s.at(i) == s.at(i + 1)) {
      cout << "Bad" <<endl;
      return 0;
    }
  }
  cout << "Good" << endl;
  return 0;
}

Measured memory_bytes: 256