akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  ll k, t; cin >> k >> t;
  const ll MAX = 100;
  vector<ll> a(t); rep(i, t) cin >> a[i];

  ll ans = 0, bef = -1;
  rep(i, k) {
    ll maxv = 0, maxj = -1;
    rep(j, t) {
      if (j == bef) continue;
      if (a[j] > maxv) {
        maxj = j;
        maxv = a[j];
      }
    }
    if (maxj == -1) {
      maxj = bef;
      maxv = a[maxj];
    }
    // debug3(bef, maxj, maxv);
    if (maxj == bef) ans++;
    a[maxj]--;
    bef = maxj;
  }
  outl(ans);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 384
def main():
    
    M = 10**9 + 7
    
    def ncr(n, r, mod=M):
        upp, low = 1, 1
        for i in range(r):
            upp = upp * (n-i) % mod
            low = low * (r-i) % mod
        return upp * pow(low, mod-2, mod) % mod
    
    x, y = map(int, input().split())
    if (x + y) % 3:
        print(0)
        return
    
    n = (x + y) // 3
    
    if x - n < 0 or y - n < 0:
        print(0)
        return
    
    print(ncr(n, x-n))

if __name__ == "__main__":
    main()


Measured memory_bytes: 38640
/*
Implementation of Kruscal's algorithm

Nodes of the graph are 0-indexed
*/

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

////////// BEGIN //////////

struct Kruscal {

    struct UnionFind{
        vector<int> par;
        vector<int> rank;

        UnionFind(int size) {
            par = vector<int>(size);
            rank = vector<int>(size);

            for (int i = 0; i < size; ++i) {
                par[i] = i;
                rank[i] = 0;
            }
        }

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

        void unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;
            if (rank[x] > rank[y]) {
                par[y] = x;
            } else {
                par[x] = y;
                if (rank[x] == rank[y]) ++rank[x];
            }
        }

        bool same(int x, int y) {
            return find(x) == find(y);
        }
    };

    struct Edge {
        int from, to, cost;

        Edge(){}
        Edge(int from, int to, int cost):
        from(from), to(to), cost(cost) {}

        bool operator<(const Edge& e) const {
            return cost < e.cost;
        }
    };

    int n;
    vector<Edge> edges;

    Kruscal() {}
    Kruscal(int size):n(size) {}

    void add_edge(int from, int to, int cost) {
        edges.emplace_back(from, to, cost);
    }

    void input(int m) {
        for (int i = 0; i < m; ++i) {
            int from, to, cost;
            cin >> from >> to >> cost;
            add_edge(from, to, cost);
        }
    }

    long long mincost() {
        sort(edges.begin(), edges.end());
        UnionFind uf(n);
        long long cost = 0;
        for (auto& e : edges) {
            if (!uf.same(e.from, e.to)) {
                cost += e.cost;
                uf.unite(e.from, e.to);
            }
        }

        return cost;
    }
};

////////// END //////////

int main () {
    int n, m;
    cin >> n >> m;
    Kruscal kr(n);
    kr.input(m);
    cout << kr.mincost() << endl;
}


Measured memory_bytes: 4448
import bisect as bis
n, m = map(int, input().split())
idx = lambda x: x-1
p, y = [], []
for _ in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
val = [[] for _ in range(n)]
for i, j in zip(p, y):
    val[idx(i)].append(j)
for i in range(n):
    val[i].sort()
for i in range(m):
    v = p[i]
    id = bis.bisect_right(val[idx(v)], y[i])
    print(str(v).zfill(6) + str(id).zfill(6))

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<long long> a(n+1);
	for(int i=0;i<=n;i++) cin >> a[i];
	
	long long noko=1;
	for(int i=0;i<=n;i++){
		if(noko<a[i]){
			cout << -1 << "\n";
			return 0;
		}
		noko-=a[i];
		if(noko<(1LL<<55)) noko*=2;
	}
	
	long long res=0;
	vector<long long> son(n+1);
	noko=1;
	for(int i=0;i<=n;i++){
		son[i]=noko;
		noko-=a[i];
		if(noko<(1LL<<55)) noko*=2;
	}
	
	long long v=0;
	for(int i=n;i>=0;i--){
		v+=a[i];
		v=min(v,son[i]);
		res+=v;
	}
	cout << res << "\n";
	return 0;
}

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


struct point{
	int x,y;
	point(int x = 0,int y = 0):x(x),y(y){
	}
};

point p[10];
double sb[10][10];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		int x,y;
		cin >> p[i].x >> p[i].y;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			sb[i][j] = sqrt((p[i].x - p[j].x) *(p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
		}
	}
	double ans = 0;
	int sbb = 1;
	for(int i = 1; i < n; i++){
		sbb = sbb * i;
	}
	for(int i = 1; i < n; i++){
		for(int j = i + 1; j <= n; j++){
			ans = ans + sbb * sb[i][j];
		}
	}
	printf("%.10lf",ans / sbb / n * 2);
	return 0;
}

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

using namespace std ;

char s[ 100010 ] ;
int n ; 

int main() {
	scanf( "%s" , s + 1 ) ;
	n = strlen( s + 1 ) ;
	int cnt = 0 ;
	for( int i = 2 ; i <= n ; ) {
		if( s[ i ] != s[ i - 1 ] ) {
			cnt ++ ;
			i ++ ;
			while( s[ i ] == s[ i - 1 ] ) i ++ ;
		} else i ++ ; 
	}
	printf( "%d\n" , cnt ) ;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i = ll(a); i <= ll(b); i++)
int main()
{
	ll n,x,k,cnt=0,total=0,ans=0,distance,imp;
	cin>>k>>n;
	vector<ll> a;
	REP(i,0,n-1)
	{
		cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	ans=a.back()-a.front();
	REP(i,1,a.size()-1)
	{
		ans=min(ans,k-(a[i]-a[i-1]));
	}
	cout<<ans;
}

Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int main() {
  while(1){
    int n,q;
    cin>>n>>q;
    --q;
    if(!n)break;
    map<int,int> m;
    REP(i,n){
      int d;
      cin>>d;
      REP(j,d){
        int k;
        cin>>k;
        ++m[k];
      }
    }
    int ans = 0;
    for(auto p:m){
      if(p.second > q){
        ans = p.first;
        q = p.second;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);

    rep(i,b) cout << a;
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if (a == 1) a += 20;
  if (b == 1) b += 20;
  if(a > b) cout << "Alice" << endl;
  else if(a < b) cout << "Bob" << endl;
  else cout << "Draw" << endl;
}


Measured memory_bytes: 256
// class point	の練習（クラスの高度な実装）
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

typedef long long llong;
using namespace std;

int main() {
	double a, b;
	int c;
	cin >> a >> b >> c;
	double pi = 3.14159265358979323846;
	double S = 0.5*a*b*sin(c*pi / 180);
	double L = a + b + sqrt(a*a + b * b - 2 * a*b*cos(c*pi / 180));
	double h = S * 2 / a;
	cout << fixed << setprecision(10) << S << endl << L << endl << h << endl;
	return 0;
}



Measured memory_bytes: 3588
def a(H):
    global ans
    global dic
    if H // 2 in dic:
        add = 2 * ans + 1
        ans = add
        dic[H] = add
    else:
        a(H//2)
        a(H//2)

H = int(input())
dic = {}
dic[1] = 1
ans = 1
if H != 1:
    a(H)
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<string, int> P;
 
bool compare(P s1, P s2){
  if(s1.first.size() < s2.first.size()) return true;
  else if(s1.first.size() > s2.first.size()) return false;
  else{
    if(s1.first < s2.first) return true;
    else return false;
  }
}

int main(){
  map<string, int> data;
  vector<P> ans;
  
  int n;
  cin >> n;
  string s;
  int t;
  for(int i = 0 ; i < n ; i++){
    cin >> s >> t;
    data[s] += t;
  }
   
  for(map<string, int>::iterator it = data.begin() ; it != data.end() ; it++){
    ans.push_back(*it);
  }
   
  sort(ans.begin(), ans.end(), compare);
   
  for(int i = 0 ; i < ans.size() ; i++){
    cout << ans[i].first << ' ' << ans[i].second << endl;
  }
  return 0;
}

Measured memory_bytes: 1236
#include<iostream>
#include<string>
using namespace std;
int main(){
    string str,word;
    int count=0;
    cin >> word;
    
    for(int i=0; i<word.size(); i++)
        if(word[i]>='A' && word[i]<='Z'){
            word[i]+=('a'-'A');
        }
    
    while(cin >> str){
        if(str=="END_OF_TEXT") break;
        for(int i=0; i<str.size(); i++){
            if(str[i]>='A' && str[i]<='Z') {
                str[i]+=('a'-'A');
            }
        }
        if(word==str) count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 3156
s = list(map(int, input().strip().split(' ')))
A = list(map(int, input().strip().split(' ')))
N = s[0]
M = s[1]
deadline = 0

for i in range(M):
    deadline = deadline + A[i]
    
if deadline > N:
    print('-1')
else:
    ans = N - deadline
    print(ans)

Measured memory_bytes: 9888
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int>P;
	vector<int>M;

	for (int i = 0;i<N;++i) {
		int num;
		cin >> num;
		if (num > 0) {
			P.push_back(num);
		}
		else {
			M.push_back(-num);
		}
	}
	sort(M.begin(),M.end());
	if (0 == P.size()) {
		cout << M[K - 1];
		return 0;
	}
	if (0 ==M.size()) {
		cout << P[K - 1];
		return 0;
	}
	int ans = 1e9;
	for (int i = 0;i<=K;++i) {
		if (i<=P.size()  && (K-i)<=M.size()) {
			ans = min(ans ,P[i - 1]+M[K-i-1]+min(P[i - 1] , M[K - i - 1]));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=LONG_LONG_MAX;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,t; cin>>n>>t;
    ll arr[n][2];ll maxi=0;
  for(ll i=0;i<n;i++)
  {
   cin>>arr[i][0]>>arr[i][1]; maxi+=arr[i][1];
  } 
  ll dp[maxi+1]; for(ll i=0;i<=maxi;i++) dp[i]=INF;
  for(ll i=0;i<n;i++)
  {
   for(ll j=maxi;j>=0;j--)
    {
     if(arr[i][1]>=j)
       dp[j]=min(dp[j],arr[i][0]);
     else if(dp[j-arr[i][1]]!=INF)
       dp[j]=min(dp[j],dp[j-arr[i][1]]+arr[i][0]);
    }
  }
  ll result=0;
  for(ll j=1;j<=maxi;j++)
  {
   if(dp[j]<=t)
   { 
   result=j;
   }
  }
  cout<<result;
    return 0;
}


Measured memory_bytes: 4376
def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def solve():
    Q = int(input())
    primes = set(eratosthenes(10 ** 5))
    like_2017 = [0] * (10 ** 5 // 2)
    for i in range(3, 10 ** 5, 2):
        if i in primes and (i + 1) // 2 in primes:
            like_2017[i // 2] = like_2017[i // 2 - 1] + 1
        else:
            like_2017[i // 2] = like_2017[i // 2 - 1]
    for _ in range(Q):
        l, r = map(int, input().split())
        if l == 1:
            l = 2
        if r == 1:
            r = 2
        ans = like_2017[r // 2] - like_2017[l // 2 - 1]
        print(ans)


if __name__ == '__main__':
    solve()


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

struct Pair{
    int a;
    int b;

    Pair(int x, int y) {
        this->a = x;
        this->b = y;
    }
};

int main() {
    int t;
    std :: cin >> t;

    if(t % 1000) std :: cout << 1000 - t % 1000 << '\n';
    else std :: cout << 0 << '\n';
}

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

using namespace std;
using ll = long long int;
constexpr ll M = 1e9 + 7;
inline ll sum_1(const ll n) { return ((n * (n + 1)) / 2) % M; }
inline ll sum_2(const ll n) { return ((n * (n + 1) * (2 * n + 1)) / 6) % M; }
inline ll sum_3(const ll n) { return (((n * (n + 1)) / 2) % M * ((n * (n + 1)) / 2) % M) % M; }
inline ll sum_1(const ll i, const ll j) { return (sum_1(j) - sum_1(i - 1) + M) % M; }
inline ll sum_2(const ll i, const ll j) { return (sum_2(j) - sum_2(i - 1) + M) % M; }
inline ll sum_3(const ll i, const ll j) { return (sum_3(j) - sum_3(i - 1) + M) % M; }

ll pow_f(ll b, ll e) {
    ll ans = 1;
    b = b % M;
    while (e) {
        if (e & 1) {
            ans = (ans * b) % M;
        }
        b = (b * b) % M;
        e >>= 1;
    }
    return ans;
}

ll nCr(ll n, ll r) {
    if (r > n || n < 0 || r < 0) { return 0; }
    if (n == r || r == 0) { return 1; }
    r = min(r, n - r);
    ll ans = 1;
    for (ll i = 1; i <= r; ++i) {
        ans = (ans * (n - i + 1)) / (i);
    }
    return ans;
}

ll nCr(tuple<ll, ll> t) {
    auto n = get<0>(t);
    auto k = get<1>(t);
    return nCr(n + k - 1, k);
}

template <typename T>
void print(const T &v) {
    cout << v << " ";
}

template <typename T>
void print(const vector<T> &v) {
    for (auto &i : v) {
        print(i);
    }
    cout << endl;
}

map<pair<ll, ll>, ll> m;

ll dp(ll i, ll j, vector<ll> &A) {
    if (m.find({i, j}) != m.end()) {
        return m[{i, j}];
    }
    if (i < 0 || j < 0) {
        return LLONG_MIN;
    }
    if (j <= i / 2) {
        if (i == 0 && j == 0) {
            return A[0];
        } else if (i >= 1 && j == 0) {
            ll temp = max(A[i], dp(i - 1, j, A));
            m[{i, j}] = temp;
            return temp;
        }

        ll temp = max(A[i] + dp(i - 2, j - 1, A), dp(i - 1, j, A));
        m[{i, j}] = temp;
        return temp;
    } else {
        return LLONG_MIN;
    }
}

void solve() {
    ll n;
    cin >> n;

    vector<ll> A(n);
    for (auto &i : A) {
        cin >> i;
    }

    ll num = n / 2;

    cout << dp(n - 1, num - 1, A) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef D_LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif

    solve();

    return 0;
}

Measured memory_bytes: 33016
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<pi, int> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int K;
vector<ppi> G[MAX_N][10];
int d[MAX_N][10];

void solve() {
	cin >> K;
	rep(i, 0, K) {
		rep(j, 0, 10) {
			d[i][j] = inf;
		}
	}
	d[1][1] = 1;
	rep(i, 0, K) {
		rep(j, 0, 10) {
			if(j != 9) G[i][j].pb(make_pair(pi((i + 1) % K, j + 1), 1));
			G[i][j].pb(make_pair(pi(i * 10 % K, 0), 0));
		}
	}
	deque<pi> que;
	que.push_back(pi(1, 1));
	while(!que.empty()) {
		pi p = que.front(); que.pop_front();
		rep(i, 0, sz(G[p.fst][p.sec])) {
			ppi tp = G[p.fst][p.sec][i];
			if(d[tp.fst.fst][tp.fst.sec] > d[p.fst][p.sec] + tp.sec) {
				d[tp.fst.fst][tp.fst.sec] = d[p.fst][p.sec] + tp.sec;
				if(tp.sec == 0) que.push_front(tp.fst);
				else que.push_back(tp.fst);
			}
		}
	}
	cout << d[0][0] << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 154752
N = int(input())
AWTR = [0,0,0,0]
for i in range(N):
    T = input()
    AWTR["AWTR".index(T[0])] += 1
A,W,T,R = AWTR
print(f"""AC x {A}
WA x {W}
TLE x {T}
RE x {R}
""")

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

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using pii = std::pair<int, int>;
using namespace std;

int H, W;
vec<vec<char>> S;
vec<vec<int>> C;

void solve() {
  REP(y, H) {
    REP(x, W) {
      if (S[y][x] == '#') {
        continue;
      }
      int cost = 0;
      for (int dy = -1; dy <= 1; dy++) {
        for (int dx = -1; dx <= 1; dx++) {
          const int nx = x + dx, ny = y + dy;
          if (0 <= nx && nx < W && 0 <= ny && ny < H && S[ny][nx] == '#') {
            cost++;
          }
        }
      }
      C[y][x] = cost;
    }
  }
  REP(y, H) {
    REP(x, W) {
      if (C[y][x] == -1) {
        cout << '#';
      }
      else {
        cout << C[y][x];
      }
    }
    cout << endl;
  }
}

int main() {
  cin >> H >> W;
  S.resize(H);
  C.resize(H);
  REP(y, H) {
    S[y].resize(W);
    C[y].resize(W);
    REP(x, W) {
      cin >> S[y][x];
      C[y][x] = -1;
    }
  }
  solve();
  return 0;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    tolerance = (k - 1)
    cnt = 0
    for i in range(1, n + 10):
        if k + tolerance * (i - 1) < n:
            cnt += 1
        else:
            cnt += 1
            break

    print(cnt)


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

int main() {
    int T, D, L;
    while (cin >> T >> D >> L, T) {
        vector<int> flood(T + D);
        for (int i = 0; i < T; i++) {
            int x; cin >> x;
            if (x < L) continue;
            flood[i] += 1;
            flood[i + D] -= 1;
        }
        for (int i = 1; i < T + D; i++) flood[i] += flood[i - 1];
        int cnt = 0;
        for (int i = 0; i < T - 1; i++) if (flood[i]) cnt++;
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 4264
N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] == L[j] or L[j] == L[k] or L[k] == L[i]:
                continue
            if L[i] + L[j] > L[k] and L[j]+L[k] > L[i] and L[i]+L[k] > L[j]:
                ans += 1
print(ans)

Measured memory_bytes: 68184
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>

int main()
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if (a==b&&b==c&&a==c)
	{
		printf("Yes");
		return 0;
	}
	printf("No");
	return 0;
}

Measured memory_bytes: 256
import sys


def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(2)]
    first = [0] * N
    second = [0] * N
    first[0] = A[0][0]
    second[N-1] = A[1][N-1]
    for i in range(1, N):
        first[i] = first[i-1] + A[0][i]
        second[N - 1- i] = second[N - i] + A[1][N - 1- i]    
    maxPoint = 0
    for i in range(N):
        maxPoint = max(maxPoint, first[i] + second[i])
    print(maxPoint)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,countAC = 0,countWA = 0, countTLE = 0, countRE = 0;
  string s;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> s;
    if(s == "AC"){
      countAC++;
    }else if(s == "WA"){
      countWA++;
    }else if(s == "TLE"){
      countTLE++;
    }else if(s == "RE"){
      countRE++;
    }
  }
  cout << "AC x " << countAC << endl;
  cout << "WA x " << countWA  << endl;
  cout << "TLE x " << countTLE << endl;
  cout << "RE x " <<  countRE << endl;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

const double PI = 3.14159265358979323846;

int main() {
    int A, B, H, M;
    cin >> A >> B >> H >> M;
    double radA = 2 * PI * ((H * 60 + M) / 720.0);
    double radB = 2 * PI * (M / 60.0);

    long double ans = (long double) (A * A + B * B) - (long double) (2 * A * B) * cosl(radA - radB);
    printf("%20.20Lf\n", sqrtl(ans));
}


Measured memory_bytes: 4144
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

int n,s;
int sum(int S) {
    int res = 0;
    rep(i,10) if((S>>i)&1) res+=i;
    return res;
}
int dfs(int S,int cnt) {
    if(cnt==n) {
        if(sum(S)==s) return 1;
        else return 0;
    }
    int res=0;
    rep(i,10) {
        if(!(S>>i)&1) {
            res+=dfs(S|(1<<i),cnt+1);
        }
    }

    return res;
}
void solve() {
    cout<<dfs(0,0)<<endl;
}
int main() {
    while(cin>>n>>s) {
        if(n+s==0) break;
        solve();
    }
    return 0;
}

Measured memory_bytes: 1160
n,m=map(int,input().split())
s=[list(input()) for i in range(n)]
ans=[[10**9+7]*m for i in range(n)]
ans[0][0]=int(s[0][0]=='#')
for i in range(n):
    for j in range(m):
        if i>0:
            #ans[i][j]=min(ans[i][j]+ans[i-1][j]+int(s[i-1][j]=='.' and s[i][j]=='#'))
            ans[i][j]=min(ans[i][j],ans[i-1][j]+int(s[i-1][j]=='.'and s[i][j]=='#'))
        if j>0:
            ans[i][j]=min(ans[i][j],ans[i][j-1]+int(s[i][j-1]=='.' and s[i][j]=='#'))
print(ans[n-1][m-1])             
               

Measured memory_bytes: 43632
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanFloat64() float64 {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return float64(a)
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//•*¨*•.¸¸♪func•*¨*•.¸¸♪

//•*¨*•.¸¸♪main•*¨*•.¸¸♪

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	hs := scanInts(n)

	pre := 0
	ans := 0
	for i := 0; i < n; i++ {
		if pre<=hs[i] {
			ans++
			pre=hs[i]
		}
	}

	fmt.Println(ans)

}


Measured memory_bytes: 640
#include<stdio.h>
int main(){
	int h1, h2, m1, m2, k;
	if(scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k) == 5){
		printf("%i\n", h2 * 60 + m2 - (h1 * 60 + m1) - k);
		return 0;
	}
}


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

int main()
{
	int N,min;
	cin>>N;
	
	int A[N],M[N]={};
	
	for(int i=0;i<N;i++)
		cin>>A[i];
	
	for(int i=0;i<N;i++){
		while(A[i]%2==0){
			A[i]/=2;
			M[i]++;
		}
	}
	
	min=M[0];
	for(int i=1;i<N;i++){
		if(min>M[i])
			min=M[i];
	}	
		
	cout<<min<<endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static class Task {

        private boolean isOk(int num, boolean[] dislikes) {
            while (num > 0) {
                int curDigit = num % 10;
                if (dislikes[curDigit]) {
                    return false;
                }
                num /= 10;
            }
            return true;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] arr = new int[k];
            boolean[] dislikes = new boolean[10];
            for (int i = 0; i < k; i++) {
                dislikes[in.nextInt()] = true;
            }

            int num = n;
            while (!isOk(num, dislikes)) {
                num++;
            }

            out.println(num);
        }
    }

    private static void sort(double[] arr) {
        Double[] objArr = Arrays.stream(arr).boxed().toArray(Double[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void sort(int[] arr) {
        Integer[] objArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void sort(long[] arr) {
        Long[] objArr = Arrays.stream(arr).boxed().toArray(Long[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(1, in, out);
        out.close();
    }

    public static void main(String[] args) {
        new Thread(null, () -> solve(), "1", 1 << 26).start();
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

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

    }

}

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

int main() {
    ll K;
    ll ai=7;
    cin>>K;
    for(int i=1;i<=K;i++)
    {
      if((ai%K)==0){
        cout<<i<<endl;
        return 0;
      }
      ai=(ai*10+7)%K;
    }
    cout<<"-1"<<endl;
    return 0;
}

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

int main(){
  int N,K; cin >> N >> K;
  string S; cin >> S;
  if (S.at(K - 1) == 'A'){
    S.at(K - 1) = 'a';
  } else if (S.at(K - 1) == 'B'){
    S.at(K - 1) = 'b';
  } else {
    S.at(K - 1) = 'c';}
  cout << S << endl; 
}
    
    
  


Measured memory_bytes: 256
'''
https://atcoder.jp/contests/abc088/tasks/abc088_d
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    kuro = 0
    for i in a:
        kuro += i.count('#')
    d = deque([[0,0]])
    dxy = [[0,1],[0,-1],[1,0],[-1,0]]
    a[0][0] = 1
    while d:
        x,y = d.popleft()
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<=h-1 and 0<=ny<=w-1:
                if a[nx][ny] == '.':
                    a[nx][ny] = a[x][y] + 1
                    d.append([nx, ny])
    if a[h-1][w-1] == '.':
        print(-1)
    else:
        print(h*w - a[h-1][w-1]-kuro)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
import sys
input_lines = sys.stdin.readlines()[:-1]
for input_ in input_lines:
    h, w = [int(i) for i in input_.split()]
    if w == 1:
        for i in range(h):
            print('#')
    elif h == 1:
        print('#' * w)
    else:
        out_ = '#' * w
        in_ = '{0}{1}{0}'.format('#', '.'*(w-2))
        print(out_)
        for i in range(h-2):
            print(in_)
        print(out_)
    print()


Measured memory_bytes: 5624
#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
#include <queue>

using namespace std;

int main()
{
    int n, u, k, v, dis[110];
    bool vis[110];
    memset(dis, -1, sizeof(dis));
    memset(vis, false, sizeof(vis));
    vector<int> adj[110];
    queue<pair<int, int>> que; //point, dis
    cin>>n;
    for (int i=0; i<n; i++)
    {
        cin>>u>>k;
        for (int j=0; j<k; j++)
        {
            cin>>v;
            adj[u].push_back(v);
        }
    }
    que.push({1, 0});
    vis[1]=true;
    dis[1]=0;
    while (!que.empty())
    {
        int a=que.front().first, b=que.front().second;
        que.pop();
        for (auto u : adj[a])
        {
            if (!vis[u])
            {
                vis[u]=true;
                dis[u]=b+1;
                que.push({u, b+1});
            }
        }
    }
    for (int i=1; i<=n; i++) cout<<i<<' '<<dis[i]<<'\n';
    return 0;
}



Measured memory_bytes: 3168
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <numeric>

int c()
{
    int n;
    std::cin >> n;
    
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int k = 1; k <= n; k++)
        {
            for(int m = 1; m <= n; m++)
            {
                //int myGCD = 0;
                int myGCD = std::gcd(std::gcd(i, k), m);
                sum += myGCD;
            }
        }
    }
    
    std::cout << sum;
    
    return 0;
}

int main(int argc, const char * argv[])
{
    c();
    return 0;
}

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

int main(){
    int x,n, cnt=0, j=0, j2=0;
    cin>>x>>n;
    if(n==0){
        cout<<x<<endl;
        return 0;
    }
    int p[n];

    for(int i=0; i<n; i++) cin>>p[i];

    while(true){
        for(int i=0; i<n; i++){
            if(x-cnt != p[i]){
                j++;
                if(j==n){
                    cout<<x-cnt<<endl;
                    return 0;
                }
            }
            if(x+cnt != p[i]){
                j2++;
                if(j2==n){
                    cout<<x+cnt<<endl;
                    return 0;
                }
            }
        }
        cnt++;
        j=0;
        j2=0;
    }
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    int a,b,c;
    cin >> a >> b;
    c = a * b;

    if (a % 2 == 0 || b % 2 == 0) {
        cout << "No"  << endl;
    }else {
        cout << "Yes" << endl;
    }
    

    return 0;
}


Measured memory_bytes: 256
import sys
n,k = map(int,input().split())
#if k == 0:
#    print(n**2)
 #   sys.exit
count = 0
for i in range(1,n+1):
    tmp_count = max(0,i - k)
    #print(i,n // i,tmp_count,(n // i)* tmp_count + max(0,(n % k)-k+1),max(0,(n % i)-k+1),n % i)
    count += (n // i)* tmp_count + max(0,(n % i)-k+1)

if k == 0:
    print(n**2)
else:
    print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<string, string> sP;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second



int main() {
	ll a, b;
	cin >> a >> b;
	if (max(a, b) - min(a, b) <= 1)cout << "Brown" << endl;
	else cout << "Alice" << endl;
	return 0;
}

Measured memory_bytes: 256
import copy
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]

cl = sum(c)
D = [0]*26
ans = [0]*d
T = [0]*d

for i in range(d):
    count = 0
    for j in range(26):
        D[j] += 1
    for j in range(26):
        sas = 0
        S = s[i][j]
        C = c[j]
        Ds = copy.copy(D)
        Ds[j] = 0
        dc = 0
        for k in range(26):
            dc += Ds[k]*c[k]
        sas = S - dc + sum(T[:i])
        if sas > count:
            count = sas
            ans[i] = j+1
            T[i] = count

for i in ans:
    print(i)
        

Measured memory_bytes: 9376
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to;
};


struct Trie {
	Trie* ch[2] = {};


	void add(string& str, int pos) {
		if (str.length() == pos) return;
		if (ch[str[pos] - '0'] == NULL) ch[str[pos] - '0'] = new Trie;
		ch[str[pos] - '0']->add(str, pos + 1);

	}

	ll calc(ll height) {
		ll ret = 0;
		if (ch[0] == NULL && ch[1] == NULL) return 0;
		if (ch[0]) ret ^= ch[0]->calc(height - 1);
		if (ch[1]) ret ^= ch[1]->calc(height - 1);
		if (ch[0] == NULL || ch[1] == NULL) {
			ll bai = 1;
			while (height % 2 == 0) height /= 2, bai *= 2;
			ret ^= bai;
		}
		return ret;
	}

};


int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n);

	REP(i, n) {
		scanf("%d", &a[i]);
	}
	REP(i, n) {
		scanf("%d", &b[i]);
	}
	REP(i, n) {
		scanf("%d", &c[i]);
	}

	sort(ALL(a));
	sort(ALL(b));
	sort(ALL(c));

	ll ans = 0;

	vector<ll> bb(n + 1);

	REP(i, n) {
		bb[i] = c.end() - upper_bound(ALL(c), b[i]);
	}
	for (int i = n - 2; 0 <= i; i--)
		bb[i] += bb[i + 1];

	REP(i, n) {
		ans +=  bb[upper_bound(ALL(b), a[i]) - b.begin()];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  int temp1;
  temp1=a;
  a=b;
  b=temp1;
  temp1=c;
  c=a;
  a=temp1;
  cout<<a<<" "<<b<<" "<<c;
}


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

static const int mod = 1e9 + 7;

long long dp[100005][4];
int main(){
    string s;
    cin >> s;

    dp[0][0] = 1;
    for(int i=0; i<s.size(); ++i){
        if(s[i] == 'C' || s[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            dp[i+1][2] += dp[i][2];
            dp[i+1][3] += dp[i][3];
            dp[i+1][3] += dp[i][2];
            for(int k=0; k<4; ++k) dp[i+1][k] %= mod;
        }
        if(s[i] == 'B' || s[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            dp[i+1][2] += dp[i][2];
            dp[i+1][3] += dp[i][3];
            dp[i+1][2] += dp[i][1];
            for(int k=0; k<4; ++k) dp[i+1][k] %= mod;
        }
        if(s[i] == 'A' || s[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            dp[i+1][2] += dp[i][2];
            dp[i+1][3] += dp[i][3];
            dp[i+1][1] += dp[i][0];
            for(int k=0; k<4; ++k) dp[i+1][k] %= mod;
        }
    }

    cout << dp[s.size()][3] << endl;
}

Measured memory_bytes: 3584
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int Maxn = 500010;
int n, K;
int a[Maxn], ans[Maxn];
vector <int> vec[Maxn]; int no[Maxn]; bool v[Maxn];
int mx[Maxn<<2];
bool cmp(int x, int y) { return a[x] > a[y]; }
int _max(int x, int y) { return x > y ? x : y; }
int _min(int x, int y) { return x < y ? x : y; }
priority_queue <int> q;
void build_tree(int now, int L, int R) {
	if(L < R){
		int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
		build_tree(lc, L, mid);
		build_tree(rc, mid+1, R);
		mx[now] = _max(mx[lc], mx[rc]);
	} else mx[now] = a[L];
}
void chg(int now, int L, int R, int x) {
	if(L == R){ mx[now] = 0; return; }
	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
	if(x <= mid) chg(lc, L, mid, x);
	else chg(rc, mid+1, R, x);
	mx[now] = _max(mx[lc], mx[rc]);
}
int qry(int now, int L, int R, int l, int r) {
	if(L == l && R == r) return mx[now];
	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
	if(r <= mid) return qry(lc, L, mid, l, r);
	else if(l > mid) return qry(rc, mid+1, R, l, r);
	else return _max(qry(lc, L, mid, l, mid), qry(rc, mid+1, R, mid+1, r));
}
void ins(int x) {
	if(x < 0 || x > n/K || no[x] == vec[x].size() || v[x] == true) return;
	int p = vec[x][no[x]];
	if(qry(1, 1, n, _max(1,p-K+1), _min(n,p+K-1)) == a[p]){
		no[x]++; v[x] = true;
		q.push(p);
	}
}
int main() {
	int i, j, k;
	scanf("%d%d", &n, &K);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	build_tree(1, 1, n);
	for(i = 1; i <= n; i++) vec[i/K].push_back(i);
	for(i = 0; i <= n/K; i++) sort(vec[i].begin(), vec[i].end(), cmp);
	for(i = 0; i <= n/K; i++) ins(i);
	for(i = n; i >= 1; i--){
		int x = q.top(); q.pop();
		ans[x] = i; chg(1, 1, n, x);
		v[x/K] = false;
		ins(x/K-1); ins(x/K); ins(x/K+1);
	}
	for(i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}


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

signed main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> ba(n);
	rep(i, n) {
		cin >> ba[i].second >> ba[i].first;
	}
	vector<pair<int, int>> cd(m);
	rep(i, m) {
		cin >> cd[i].first >> cd[i].second;
		cd[i].second--;
	}
	multiset<int> se;
	int now = inf;
	vector<int> rui(m);
	rep(i, m) {
		now = min(now, cd[i].second);
		rui[i] = now;
	}
	now = 0;
	rep(j, rui[m - 1]) {
		se.insert(inf);
	}
	rep(i, m - 1) {
		rep(j, rui[i] - rui[i + 1]) {
			se.insert(cd[i + 1].first);
		}
	}
	rep(i, n) {
		se.insert(cd[0].first);
		now++;
	}
	sort(ba.begin(), ba.end(), greater<pair<int, int>>());
	int all = 0;
	for(auto i: ba) {
		auto it = se.upper_bound(i.second);
		if(it != se.end()) {
			all += i.first;
			se.erase(it);
		}
	}
	cout << all << endl;
}


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

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

using namespace std;

int main(){
  long double q,h,s,d;cin>>q>>h>>s>>d;
  ll n;cin>>n;

  vector<long double> a(4);
  a[0] = q/0.25;
  a[1] = h/0.5;
  a[2] = s;
  a[3] = d/2;
  sort(a.begin(), a.end());
//  rep(i,4)cout<<a[i]<<' ';cout<<endl;

  ll result=0;
  rep(i, 4){
    if(a[i]==d/2){result += (n/2)*d;n%=2;}
    if(a[i]==s){result += n*s;n=0;}
    if(a[i]==h/0.5){result += (n/0.5)*h;n=0;}
    if(a[i]==q/0.25){result += (n/0.25)*q;n=0;}
//cout<<result<<endl;
  }

  cout<<result;  

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void){
    int distance=0,angle=90,rotate;
    double x=0,y=0,Pi=3.141592;
    
    
    while(1){
        scanf("%d,",&distance);
        x+=distance*cos(angle*Pi/180);
        y+=distance*sin(angle*Pi/180);
        scanf("%d",&rotate);
        if(distance==0 && rotate==0) break;
        angle-=rotate;
    }
    
    printf("%d\n%d\n",(int)x,(int)y);
    return 0;
}

Measured memory_bytes: 604
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    string s;
    cin >> s;
    if ( s == "keyence" ) {
        cout << "YES" << endl;
        return 0;
    }
    rep(i, s.length()) {
        rep(j, s.length()) {
            string tmp_s = "";
            rep(k, s.length()) {
                if ( i<=k && k<=j ) {
                    continue;
                }
                tmp_s.push_back(s[k]);
            }
            if ( tmp_s == "keyence" ) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
typedef string St;


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a<=c&&c<=b) ? (St)"Yes" : (St)"No") << endl;
	
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int N = sc.nextInt();
			while (N-- > 0) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int b = sc.nextInt();
				int p = sc.nextInt();

				int min = x * b + y * p;
				double ans;
				if (b >= 5 && p >= 2) {
					ans = min * 0.8;
				} else {
					int div = x * b + y * p;
					if (b < 5) {
						div += (5 - b) * x;
					}
					if (p < 2) {
						div += (2 - p) * y;
					}
					ans = Math.min(min, div * 0.8);
				}
				System.out.println((int) ans);
			}
		}
	}
}

Measured memory_bytes: 23328