akhauriyash/Code-Regression huggingface dataset:
H, W, K = map(int, input().split())
chocolate = [input() for _ in range(H)]
cumsums = [[0] for _ in range(W)]
for w in range(W):
    for h in range(H):
        cumsums[w].append(cumsums[w][-1] + int(chocolate[h][w]))
ans = (H-1) + (W-1)
for bit in range(1 << (H-1)):
    h_splits = [0]
    temp = 0
    for l in range(H):
        if (bit >> l) & 1: h_splits.append(l+1); temp += 1
    h_splits.append(H)
    n_sp_hr = (len(h_splits) - 1)
    counter = [0] * n_sp_hr
    for w in range(W):
        admissible = True
        cumsum = cumsums[w]
        to_be_added = [0] * n_sp_hr
        for s in range(n_sp_hr):
            to_be_added[s] = cumsum[h_splits[s+1]] - cumsum[h_splits[s]]
            if to_be_added[s] > K: admissible = False; break
        if not admissible: break
        for s in range(n_sp_hr):
            counter[s] += to_be_added[s]
            if counter[s] > K: temp += 1; counter = to_be_added[:]; break
    else:
        ans = min(ans, temp)
print(ans)

Measured memory_bytes: 44268
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#define rep(i,n) for (int i=0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main(){
    int a, b, ans=1;
    cin >> a >> b;
    if(b == 1) {
        cout << 0 << endl;
        return 0;
    }
    if(a >= b){
        cout << ans << endl;
        return 0;
    }
    while(true){
        if(a*ans-ans+1 >= b) break;
        else ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
using namespace std; 
int main() { 	
    
    int n, i;
    int c[50] = {0}, v[50] = {0}, diff[50] = {0}; 
		int ans = 0;

		cin >> n;
    
		for(i = 0; i < n; i++){
    	cin >> v[i];
		}
		for(i = 0; i < n; i++){
    	cin >> c[i];
		}
		for(i = 0; i < n; i++){
    	diff[i] = v[i] - c[i];
		}
		for(i = 0; i < n; i++){
    	if(diff[i] > 0){
				ans += diff[i];
			}
		}
    
    cout << ans << endl; 
    	return 0; 
    }

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

int main(){
  	int A, B;
  	cin >> A >> B;
  	int counter=0;
  	for(int i=A;i<=B;i++){
      	if(i/10000 == i%10 && (i/1000)%10 == (i/10)%10) counter++;
    }
  	cout << counter << endl;
}

Measured memory_bytes: 3512
// 解説後
#include <algorithm>
#include <iostream>
#include <vector>

// N <= 2*10^5なので、O(N^2)ではおそらくTLEする
// => せめてO(NlogN)でやりたい
//
// チームの成績は完食にかかる時間（消化コスト*食べにくさ）の最大値
// => 成績を小さくには全体として完食にかかる時間を小さくする必要がある
// => 成績は掛け算なので一方を小さい順に、もう一方を大きい順に選ぶと最も小さくなる
// => メンバーを昇順に、食べ物を降順に選べば良い
//
// 求めたい値は成績の最小値
// => 「成績の最小値がxとなり得るか」に対して、その境界値を二分探索で計算すれば良い
//
// メンバーをA_i、食べ物をF_iとする。（ここで、i<jのとき、A_i<=A_jでありF_i>=F_j）
// 修行回数を節約しつつ完食にかかる時間をX以下とするには、各人の消化コストをB_i=X/F_iとする必要がある。
// F_i>=F_jなので、B_i<=B_jとなり、修行後の消化コストは昇順を維持する。
// => 修行後でも食べ物の割当を変えることなく成績の最小値が得られる。
// => Σ(A_i-B_i)がK以下であれば、修行によって成績をX以下にまで下げることができると分かる。
int solve_E() {
  size_t N = 0;  // チームの人数
  uint64_t K = 0;  // 修行できる最大回数
  std::cin >> N >> K;

  std::vector<uint64_t> costs(N);  // メンバーの消化コストの配列
  for (auto& cost : costs) {
    std::cin >> cost;
  }

  std::vector<uint64_t> foods(N);  // 食べ物の食べにくさの配列
  for (auto& food : foods) {
    std::cin >> food;
  }

  // 配列をソートする
  std::sort(costs.begin(), costs.end(), std::less<>{});  // 昇順
  std::sort(foods.begin(), foods.end(), std::greater<>{});  // 降順

  // 取りうる成績の最大値を計算する
  uint64_t max = 0;
  for (size_t i = 0; i < N; ++i) {
    max = std::max(max, costs[i] * foods[i]);
  }

  // 成績の最小値が取り得る境界を二分探索で探す
  uint64_t min = 0;
  while (min < max) {
    const uint64_t mid = min + (max - min) / 2;

    // 成績がx以下となるように修行できるかを確かめる
    const auto check = [&](uint64_t x) -> bool {
      uint64_t k = 0;
      for (size_t i = 0; i < N; ++i) {
        // 成績がx以下になるような修行回数を累積的に計算する
        const auto new_cost = x / foods[i];
        if (costs[i] > new_cost) {
          k += costs[i] - new_cost;
        }

        // 最大修行回数に収まらなければ、成績をx以下にできないことが分かる
        if (k > K) return false;
      }

      // K回以下で成績をx以下にできることが分かった
      return true;
    };
    if (check(mid)) {
      max = mid;
    } else {
      min = mid + 1;
    }
  }

  // 結果発表
  std::cout << min;

  return 0;
}

int main() { return solve_E(); }


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define INF (INT_MAX / 4)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  string s;
  cin >> s;
  vector<ll> ans(s.size() + 1, 0);

  for (int i = 1; i <= s.size(); i++) {
    if (s.at(i - 1) == '<') {
      ans.at(i) = ans.at(i - 1) + 1;
    }
  }

  for (int i = s.size() - 1; i >= 0; i--) {
    if (s.at(i) == '>') {
      ans.at(i) = max(ans.at(i + 1) + 1, ans.at(i));
    }
  }

  ll answer = 0;
  for (auto x : ans) {
    answer += x;
  }
  //DEBUGS(ans);
  cout << answer << "\n";
}


Measured memory_bytes: 4740
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 1; i <= (int)(n); i++)
const long long INF = 1LL << 60;
int main() 
{
    int a, b, c, d,tl,tr;
    cin >> a >> b >> c >> d;

    tl= max(a,c);
    tr= min(b,d);

    if(tr-tl <= 0)
        cout << 0 << endl;
        else
        {
            cout << tr-tl << endl;
        }
        
}

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

using namespace std;

int main(){
    int N, D;
    cin >> N >> D;

    int sighted = 2 * D + 1;
    int staff = 0;
    while(true) {
       if(sighted * staff >= N) break;
       staff++;
    }

    cout << staff << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
#include <unordered_map>
#include <map>

#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

struct e { ll to, cost; };
typedef pair<ll, ll> P;
int main() {
	int N;
	cin >> N;
	vector<vector<e> > G(N,vector<e>());
	vector<ll> d(N, INF_LL);
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a-1].push_back(e{ b-1, c });
		G[b-1].push_back(e{ a-1, c });
	}
	int Q, K;
	cin >> Q >> K; K--;
	priority_queue<P, vector<P>, greater<P>> que;
	d[K] = 0;
	que.push(P(0, K));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first)continue;
		for (int i = 0; i < G[v].size(); i++) {
			e next = G[v][i];
			if (d[next.to] > d[v] + next.cost) {
				d[next.to] = d[v] + next.cost;
				que.push(P(d[next.to], next.to));
			}
		}
	}

	for (int i = 0; i < Q; i++) {
		ll x, y;
		cin >> x >> y;
		cout << d[x-1] + d[y-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 11120
N,M=map(int,input().split())
SC=[list(map(int,input().split())) for i in range(M)]
begin=10**(N-1)
end=10**N
if N==1:
  begin=0
for i in range(begin,end):
  i=str(i)
  for s,c in SC:
    if i[s-1]!=str(c):
      break
  else:
    print(i)
    exit()
print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
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; }

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

  // テーブルを作る前処理
  /* facが普通の階乗を求めている。invが逆数を求めている。finvが逆数の階乗を求めている。*/
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;
}

int n, m;
int main() {
    cin >> n >> m;
    COMinit();
    cout << COM(n, 2) + COM(m, 2) << endl;
}

Measured memory_bytes: 12160
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
    arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
    for (auto& i : arr) {
        fill_all(i, v);
    }
}

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t D;
int32_t C[30];
int32_t S[400][30];

int32_t res[400];
void greedy1()
{
    int32_t last[40] = {};
    fill_all(last, -1);
    for (int32_t d = 0; d < D; d++)
    {
        int32_t max = S[d][0];
        int32_t max_index = 0;
        for (int32_t i = 0; i < 26; i++)
        {
            auto ss = S[d][i] - C[i]*(d - last[i]);
            if (max < ss) {
                max = ss;
                max_index = i;
            }
        }
        res[d] = max_index;
        last[max_index] = d;
    }
}

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    in >> D;
    for (size_t i = 0; i < 26; i++)
    {
        in >> C[i];
    }
    for (size_t d = 0; d < D; d++)
    {
        for (size_t i = 0; i < 26; i++)
        {
            in >> S[d][i];
        }
    }
    greedy1();

    //for (size_t d = 0; d < D; d++)
    //{
    //    out << res[d]+1 << '\n';
    //}
    for (size_t d = 0; d < D; d++)
    {
        out << (d%26) + 1 << '\n';
    }

    return 0;
}
#endif


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

const int MAX_N = 1e5+2;
const ll MX = 1e18;
int N;
ll A[MAX_N];

void solve()
{
	ll nonleaf = 1;
	for(int i=0;i<N+1;++i) {
        nonleaf -= A[i];
        if (nonleaf < 0) {
            cout << -1 << '\n'; 
			return;
        }
        nonleaf *= 2;
		if (nonleaf > MX) nonleaf = MX;
    }
    ll lower = accumulate(A,A+N+1,0LL);
	nonleaf = 1;
    ll ans = 0;
    for(int i=0;i<N+1;++i) {
        ans += min(nonleaf, lower);
        nonleaf -= A[i];
        nonleaf *= 2;
		if (nonleaf > MX) nonleaf = MX;
        lower -= A[i];
    }
    cout << ans << '\n';
}

int main() {
   	
    cin >> N;
    for(int i=0;i<N+1;++i) cin >> A[i];
	solve();	
	return 0;
}



Measured memory_bytes: 4376
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <functional>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << i << "\n"

//const ll MOD = 998244353;
const ll MOD = 1e9+7;
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n,m;
  std::cin>>n>>m;

  std::vector<std::vector<ll>> a(n,std::vector<ll>(3));

  rep(i,0,n)std::cin>>a[i][0]>>a[i][1]>>a[i][2];

  ll ans=0;

  for(ll i=(1<<3)-1;i>=0;i--){
    std::vector<ll> temp;
    rep(j,0,n){
      ll value=0;
      rep(k,0,3)value+=((i>>k)&1)?a[j][k]:-a[j][k];

      temp.push_back(value);
    }

    std::sort(all(temp),std::greater<ll>());

    ll temp2=0;
    rep(j,0,m)temp2+=temp[j];
    ans=std::max(ans,temp2);
  }

  std::cout<<ans;

  return 0;
}

Measured memory_bytes: 384
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    int solve(vector<vector<int>>& A, vector<vector<int>>& B) {
        int n = A.size();
        int m = A[0].size();
        int N = 80 * (n + m) + 1;
        const int INF = 1 << 24;
        vector<vector<bool>> dp(m, vector<bool>(N + 1, false));
        dp[0][0] = true;
        auto ndp = dp;

        auto update = [&](vector<bool>& S, vector<bool>& T, int diff) {
            int m = S.size();

            for (int i = 0; i < m; ++i) {
                if (S[i]) {
                    for (int j = -1; j < 2; j += 2) {
                        int ni = i + j * diff;
                        ni = abs(ni);
                        if (ni < m) {
                            T[ni] = true;
                        }
                    }
                }
            }
        };

        for (int i = 0; i < n; ++i) {
            for (auto& V : ndp) {
                fill(V.begin(), V.end(), false);
            }
            for (int j = 0; j < m; ++j) {
                int diff = A[i][j] - B[i][j];
                if (j - 1 >= 0) {
                    update(ndp[j - 1], ndp[j], diff);
                }
                update(dp[j], ndp[j], diff);
            }
            swap(ndp, dp);
        }
        for (int i = 0; i <= N; ++i) {
            if (dp[m - 1][i]) {
                return i;
            }
        }
        return -1;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;

    vector<vector<int>> A(h, vector<int>(w, 0));
    vector<vector<int>> B(h, vector<int>(w, 0));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> B[i][j];
        }
    }


    Solution sol;
    cout << sol.solve(A, B) << "\n";

    return 0;
}

Measured memory_bytes: 640
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = [na() for _ in range(n)]

    query = []

    for i, di in enumerate(d):
        s = di[0] - di[1]
        t = di[0] + di[1]
        query.append((s, 1, i))
        query.append((t, 0, i))

    query.sort(key=lambda x: x[1])
    query.sort()

    ans = 0
    idx = -1
    for x, st, i in query:
        if st == 0:
            if idx == i:
                idx = -1
        if st == 1:
            if idx == -1:
                idx = i
            else:
                if d[idx][0] + d[idx][1] > d[i][0] + d[i][1]:
                    idx = i
                ans += 1

    print(n - ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 84192
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

vector<ll> getPrimesFast(ll n){
    vector<ll> primes;
    if (n < 10000){
        primes.clear();
        if (n < 2){
            return primes;
        }
        primes.push_back(2);
        if (n == 2){
            return primes;
        }
        primes.push_back(3);
        if (n == 3){
            return primes;
        }
        for(ll i = 5; i <= n; i += 2){
            bool isPrime = true;
            for(int p = 0; p < (int)primes.size(); ++p){
                if (i % primes[p] == 0){
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.push_back(i);
            }
        }
        return primes;
    }
    else{
        vector<ll> sieve = getPrimesFast(sqrt(n));
    
        vector<short> isPrime(n+1, 1);
        for(int i = 0; i < (int)sieve.size(); ++i){
            for(int j = sieve[i] * 2; j <= n; j += sieve[i]){
                isPrime[j] = 0;
            }
        }

        for(int i = 2; i <= n; ++i){
            if (isPrime[i]){
                primes.push_back(i);
            }
        }
        return primes;
    }
}

int main(void)
{
    cin.sync_with_stdio(false);
    int n;

    auto primes = getPrimesFast(1000000);

    while(cin >> n) {
        auto itr = upper_bound(ALL(primes), n);
        cout << itr - primes.begin() << endl;
    }
    return 0;
}

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

int main(){
    int N; cin >> N;
    vector<long long> A(N), B(N);
    ll sum = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        sum += A[i];
 //       SUM[i] = sum;
    }
    B[0] = sum;
    //cout << sum << endl;
    for(int i = 1; i < N; i += 2){
        B[0] -= 2 * A[i];
    }
    for(int i = 1; i < N; i++){
        B[i] = 2 * A[i-1] - B[i-1];
    }
    for(int i = 0; i < N; i++){
        cout << B[i];
        if(i != N - 1) cout << " ";
        else cout << endl;
    }
}


Measured memory_bytes: 2944
using System;
using System.Linq;

namespace ABC148
{
    class C
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];

            long res = CalcLCM(A, B);
            Console.WriteLine(res);
        }

        public static long CalcGCD(long a, long b)
        {
            if (b == 0) { return a; }
            return CalcGCD(b, a % b);
        }

        public static long CalcLCM(long a, long b)
        {
            return a * b / CalcGCD(a, b);
        }

    }
}


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

typedef long double ld;                                   // XD
#define int long long   
#define PB push_back 
#define all(x) (x).begin(),(x).end()
#define ii pair <int,int>
#define mii map <int,int>
#define vi vector<int> 
#define vii vector< ii >
#define F first
#define S second 
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define sz(x) (int)((x).size())
const double pi=2*acos(0.0);
inline void io(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);         
#endif
}

const int mod = 1e9+7;
const int INF = 1e18;
const int maxn = 2e5+5;


void solve(){
	int n; cin>>n;
	int cur = 7%n;
	map <int, int> mp;
	int ans = 1;
	while(true){
		if(!cur) break;
		if(mp[cur]){
			cout<<-1; return;
		}
		mp[cur]++;
		cur *=10; cur += 7;
		cur = cur%n; ++ans;
	}
	cout<<ans;
}
signed main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //io();
    cout<<setprecision(16);
    
    int tc=1;// cin>>tc; 
    while(tc--){
        solve();cout<<'\n';
    }
    return 0;
}



Measured memory_bytes: 66092
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=(ll)1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    string N;
    cin >> N;
    ll sum=0;
    for(char p: N){
        ll r=p-'0';
        sum+=r;
    }
    if(sum%9==0)prt("Yes");
    else prt("No");

    return 0;
}



Measured memory_bytes: 3772
#include <iostream>
#include <map>
using namespace std;
#define MOD 1000000007

void solve(){
  int n; cin >> n;
  map<int,int> mp;
  int flag = 0;
  for(int i = 0; i < n; ++i) {
	int tmp; cin >> tmp;
    mp[tmp]++;
    if(n%2 == 0 && tmp%2==0){
      cout << 0 << endl;
      return;
    }
    if(n%2==1 && tmp%2==1){
      cout << 0 << endl;
      return;
    }
    if(mp[tmp] >2 || mp[0] > 1) {
      cout << 0 << endl;
      return ;
    }
  }
  long long ans = 1;
  
	for(int i = 0; i < n/2; ++i){
      ans *= 2;
      ans %= MOD;
    }
    cout << ans << endl;
  }


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


Measured memory_bytes: 5884
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;

  int now = n;
  vector<int> ans;

  while (1) {
    for (int j = m; j >= 1; --j) {
      if (now - j >= 0 && s[now - j] == '0') {
        // cout << now << " " << j << endl;
        now -= j;
        ans.eb(j);
        if (now == 0) {
          reverse(all(ans));
          cout << ans << endl;
          return;
        }
        break;
      }
      if (j == 1) {
        cout << -1 << endl;
        return;
      }
    }
  }
}


Measured memory_bytes: 1096
def xor(b):
    if b%4==0:
        val = b
    else:
        if b%4==1:
            val=1
        else:
            if b%4==2:
                val=b+1
            else:
                val = 0
    return val


a,b = map(int,raw_input().strip().split())

val1 = xor(b)
val2 = xor(a)

print(val1^val2^a)

Measured memory_bytes: 2568
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int n,p;
int nums[59];
ll dp[59];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n>>p;
    rep(i,n) cin>>nums[i];
    rep(i,n) nums[i]%=2;
    
    dp[0]=1;
    rep(i,n){
        int x=nums[i];
        for(int j=50;j-x>=0;j--){
            if(dp[j-x]) dp[j]+=dp[j-x];
        }
    }
    
    ll ans=0;
    rep(i,51){
        if((i%2)==p) ans+=dp[i];
    }
    cout1(ans)
}

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

int N;
#define MAXN 200000
long long A[MAXN];
long long R;

int main() {
  cin >> N; for(int i = 0; i < N; ++i) cin >> A[i];
  int l = 0, r = 0, x = 0, s = 0;
  while(true) {
    if(r < N && (x ^ A[r]) == s + A[r]) {
      x ^= A[r]; s += A[r]; ++r;
    } else {
      R += r - l;
      x ^= A[l]; s -= A[l]; ++l;
      if(l == N) break;
    }
  }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rrep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define Size(x) ((int)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
long long MOD = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo,gyakugen
//mint

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll N,M;
        cin>>N>>M;
        vl p(6,1);
        rep(i,5){
            p[i+1]=p[i]*2;
        }
        cout<<p[M]*(100*(N-M)+1900*M)<<endl;
    }

Measured memory_bytes: 256
// ~/Remember,remember the 6th of March

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double  EPS = 1e-8;
const ll MOD = 1000000007;
const int N = 100000 + 7;

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<max(max(a-b,a+b),a*b)<<endl;

    return 0;
}


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

int main(){
    string num;
    while(1){
        cin>>num;
        if(num=="0")break;

        int sum=0;

        for(int i=0;i<num.size();i++){
            sum += num[i]-'0';    
        }
        cout<<sum<<endl;
    }
    return 0;
}


Measured memory_bytes: 3160
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
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;}

int a,b,c;
inline void solve(){
  IN3(a,b,c);
  if(a+b==c||b+c==a||c+a==b)OUT("Yes");
  else OUT("No");
}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

socre = 0
his = [0] * len(C)

for i in range(D):
    t = int(input())
    t -= 1
    his[t] = i + 1
    sat = 0
    for j in range(len(C)):
        sat += C[j] * (i - his[j] + 1)
    socre += S[i][t] - sat

    print(socre)

Measured memory_bytes: 9316
#include<stdio.h>
#include<stdlib.h>

int main(){
  int i,j;
  int N;
  int KTK;
  int count=0;
  int Alength;
  
  scanf("%d",&N);
  //if(N>100||N<1){
  //  printf("N is wrong\n");
  //  exit(0);
  //}
  
  int A[N];
  
  Alength = sizeof(A)/sizeof(int);
  
  for(i=0;i<=Alength-1;i++){
    scanf(" %d",&A[i]);
  }

  A[Alength]='\0';

  for(i=0;i<=Alength-1;i++){
    for(j=Alength-1;j>=i+1;j--){
      if(A[j]<A[j-1]){
	KTK=A[j];
	A[j]=A[j-1];
	A[j-1]=KTK;
	count++;
      }
    }
  }

  for(i=0;i<Alength-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d",A[i]);
  printf("\n");
  printf("%d\n",count);

  return 0;
}
	



Measured memory_bytes: 2124
n = int(input())
A = list(map(int, input().split()))

from collections import defaultdict
d = defaultdict(lambda: (n, 0))
for i, a in enumerate(A):
    min_id, cnt = d[a]
    d[a] = (min(min_id, i), cnt+1)

B = list(d.items())
B.sort()

#print(B)

ans = [0]*n
while True:
    a1, (m1, c1) = B.pop()
    if not B:
        ans[m1] += c1*a1
        break
    a2, (m2, c2) = B[-1]
    ans[m1] += c1*(a1-a2)
    B[-1] = (a2, (min(m1, m2), c1+c2))

print(*ans, sep='\n')

Measured memory_bytes: 82232
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>


using namespace std;

int main(int argc, char *argv[])
{
	int a, b, c, d;
	int count_t, count_a;
	cin >> a >> b >> c >> d;

	if (c % b != 0)
		count_t = c / b + 1;
	else
		count_t = c / b;

	if (a % d != 0)
		count_a = a / d + 1;
	else
		count_a = a / d;

    if (count_t <= count_a)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;


	return 0;
}

Measured memory_bytes: 3636
import java.util.HashSet;
import java.util.Set;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        int a = s;
        int index = 1;
        while (!set.contains(a)) {
            set.add(a);
            if (a % 2 == 0) {
                a /= 2;
            } else {
                a = 3 * a + 1;
            }
            index++;
        }
        System.out.println(index);
        sc.close();
    }
}

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

const double PI = acos(-1);
const double EPS = 1e-15;
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
const ll MOD1 = 998244353;
//typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int h,w,n,sh,sw;
string s,t;
string d = "LURD";
int dh[4] = {0,-1,0,1};
int dw[4] = {-1,0,1,0};
map<char,int> mp;

bool hoge(int dir) {

  int bk = (dir+2)%4;

  int pos = (dir&1 ? sh:sw);

  for (int i = 0; i < n * 2; i++) {
    if (i & 1) {
      if (mp[t[i/2]] == bk) {
        pos += (dir < 2 ? 1 : -1);
        if (pos == 0) pos++;
        if (pos == (dir&1?h+1:w+1)) pos--;
      }
    } else {
      if (mp[s[i/2]] == dir) {
        pos += (dir < 2 ? -1 : 1);
      }
      //cout << "*" << pos << endl;
      if (pos == 0) return 0;
      if (pos == (dir&1?h+1:w+1)) return 0;
    }
  }

  return 1;
}

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

  cin >> h >> w >> n >> sh >> sw >> s >> t;

  bool f = 1;

  mp['L'] = 0;
  mp['U'] = 1;
  mp['R'] = 2;
  mp['D'] = 3;

  //落ちたら0を返す
  f &= hoge(0);
  //cout << f << endl;
  f &= hoge(1);
  //cout << f << endl;
  f &= hoge(2);
  //cout << f << endl;
  f &= hoge(3);
  //cout << f << endl;

  cout << (f? "YES" : "NO") << endl;

  return 0;
}


Measured memory_bytes: 920
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ROCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define f first
#define sec second
using namespace std;
using namespace __gnu_pbds;
const long long int linf =(long long)9223372036854775807;
const int dx[8] =  {0,0,1,-1,1,-1,1,-1},dy[9] = {1,-1,0,0,1,-1,-1,1};
typedef long long int ll;

const int N=3e3+5;
double dp[N][N],arr[N];
int n,vis[N][N];

double solve(int idx,int cnttail,int cnthead){
  if(idx==n){
      if(cnthead>cnttail)return 1.0;
      else return 0;
  }if(vis[idx][cnthead])return dp[idx][cnthead];
  double head=solve(idx+1,cnttail,cnthead+1)*arr[idx];
  double tail=solve(idx+1,cnttail+1,cnthead)*(1-arr[idx]);
  vis[idx][cnthead]=1;
  return dp[idx][cnthead]=head+tail;
}

int main()
{
    ROCK;
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    cout<<setprecision(10)<<solve(0,0,0)<<endl;
    return 0;
}






Measured memory_bytes: 104832
import java.lang.reflect.Array;
import java.util.*;

public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int X = sc.nextInt();
	int array[] = new int [X];
	int count = 0;
	
	//int array2[] = new int[X];
	
	for(int j=0;j<X;j++) {
		array[j] = sc.nextInt();
		//array2[j] = sc2.nextInt();
		//System.out.println(array[j]);
	}
	
	for(int i=0;i<X;i++) {
		if(array[i]!=i+1)
		count = count+1;
	}
	if(count==2||count==0) {
		System.out.println("YES");
	}else {
		System.out.println("NO");
	}
	
}
}


Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AGC30A
{
    class Program
    {
        static void Main(string[] args)
        {
           string input = Console.ReadLine();
            string[] data = input.Split(' ');
            int A = int.Parse(data[0]);
            int B = int.Parse(data[1]);

            if (B % A == 0)
                Console.WriteLine(B + A);
            else
                Console.WriteLine(B - A);
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
typedef pair<int, int> P;
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    P p[100010];
    rep(i, N) {
        cin >> p[i].first;
        p[i].second = -i;
    }
    int ans[100010] = {};
    sort(p, p + N, greater<P>());
    int cnt = 1;
    int idx = -p[0].second;
    rep(i, N) {
        idx = min(idx, -p[i].second);
        int diff = p[i].first;
        if(i + 1 < N) diff -= p[i + 1].first;
        ans[idx] += diff * cnt;
        //cout << p[i].first << " " << p[i + 1].first << " " << cnt << " " << idx << endl;
        cnt++;
    }
    rep(i, N) {
        cout << ans[i] << endl;
    }


    return 0;
}


Measured memory_bytes: 3456
N, A, B = map(int, input().split())

def findSumOfDigits(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n = n // 10
    return sum

total = 0

for i in range(N+1):
    sum = findSumOfDigits(i)
    if (A <= sum <= B):
        total += i

print(total)

Measured memory_bytes: 3060
/*  TAHMID RAHMAN
    DAMIAN FOREVER
     MATH LOVER
    NEVER GIVE UP
*/
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define pb push_back
#define fi first
#define se second
#define in insert
#define mp make_pair
#define GCD(a,b) __gcd(a,b);
#define endl "\n"
#define FRU freopen("out.txt","w",stdout)
#define FRO freopen("in.txt","r",stdin)
#define INFLL 9223372036854775807
#define debug 0
#define MAXN   100001
#define ar array
const int mxN=2e5;
const int MOD=1e9+7;
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
//Don't hesitate to ask me if you don't understand my code.......Happy coding,Tahmid...;
int main()
{
    fastio;
    ll n,i,co=0;
    ll a,b;
    cin>>n>>a>>b;
    if((a-b)%2)
    {
        cout<<"Borys"<<endl;
    }
    else
        cout<<"Alice"<<endl;


}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    ((ll)1ll<60)
#define INF     ((int)1<<30)
#define EPS     (1e-9)
#define MOD     (1000000007)
template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class T,typename I=typename T::iterator>auto&operator<<(ostream&os,T t){bool b=1;for(auto s:t)os<<(abi::__cxa_demangle(typeid(decltype(*declval<I>())).name(),0,0,0)[2]=='d'||exchange(b,0)?"":" ")<<s;return os<<endl;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int a,b;
	cin>>a>>b;
	cout<<max({a+b,a-b,a*b})<<endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,a[111]={};
	cin>>n;
	FOR(i,0,n)cin>>a[i];
	a[n]=-1;
	n++;
	int ans=0,now=-1,tmp=0;
	FOR(i,0,n){
		//cerr<<i<<" "<<now<<endl;
		if(a[i]==now){
			tmp++;
		}else{
			now=a[i];
			ans+=tmp/2;
			tmp=1;
		}
	}
	cout<<ans;
    return 0;
}


Measured memory_bytes: 256
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#n = int(input())
	h, w, k = tin()
	#s = input()
	ss = [input() for _ in range(h)]
	ret = [[0]*w for _ in range(h)]
	no_cut = 0
	cut_num = 0
	for hi, hl in enumerate(ss):
		#pa(hl)
		if hl.count('#') == 0 and no_cut >= 0:
			no_cut += 1
			#pa('gggg')
		elif hl.count('#') == 0:
			ret[hi]=ret[hi-1]
			#pa('ghggbh')
		else:
			fs = True
			cut_num += 1
			for wi, c in enumerate(hl):
				if c == '#' and fs:
					fs = False
					ret[hi][wi] = cut_num
				elif c == '#':
					cut_num+=1
					ret[hi][wi]=cut_num
				else:
					ret[hi][wi]=cut_num
			if no_cut >= 0:
				for hii in range(hi):
					ret[hii] = ret[hi]
				no_cut = -1
	for l in ret:
		print(*l)
			
					
				
				
				
			
			
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 75148
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(){
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<P> LR(M);
  vi p(Q), q(Q);
  for(int i = 0; i < M; i++){
    cin >> LR.at(i).first >> LR.at(i).second;
    LR.at(i).first--; LR.at(i).second--;
  }
  sort(ALL(LR));

  for(int i = 0; i < Q; i++){
    cin >> p.at(i) >> q.at(i);
    p.at(i)--; q.at(i)--;
  }
  
  vvi a(N, vi(N,0));
  vvi sum(N, vi(N+1,0)); //sum.at(i)はi以降に始点がある列車の終点の累積和
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      int l = LR.at(j).first, r = LR.at(j).second;
      if(l < i) continue;
      a.at(i).at(r)++;
    }
  }
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      sum.at(i).at(j+1) = sum.at(i).at(j) + a.at(i).at(j);
    }
  }

  for(int i = 0; i < Q; i++){
    int num = sum.at(p.at(i)).at(q.at(i)+1) - sum.at(p.at(i)).at(p.at(i));
    cout << num << endl;
  }
  
}

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

int main() {
    int N; cin >> N;
    vector<pair<int, int>> red(N), blue(N);
    for (int i = 0; i < N; i++) {
        cin >> red[i].first >> red[i].second;
    }
    for (int i = 0; i < N; i++) {
        cin >> blue[i].first >> blue[i].second;
    }
    sort(red.begin(), red.end());
    sort(blue.begin(), blue.end());
    int count = 0;
    vector<int> memo(N, -1);
    for (int i = 0; i < N; i++) { //blue[i]
        int it = -1; int val = -1;
        for (int j = 0; j < N; j++) { //red[i]
            if (memo[j] != -1) continue;
            if (blue[i].first > red[j].first) {
                if (blue[i].second > red[j].second) {
                    if (red[j].second > val) {
                        val = red[j].second;
                        it = j;
                    }
                }
            }
        }
        if (it != -1) {
            memo[it] ++;
            count ++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
const int mod=1000000007;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int main(){
    int n;cin>>n;
    string s1,s2;cin>>s1>>s2;
    bool pre=false;
    bool now=false;
    ll ans=1;
    for(int i=0;i<n;){
        if(s1[i]==s2[i]){
            now=true;
        }
        else{
            now=false;
        }
        if(now){
            if(i==0) (ans*=3)%=mod;
            else{
                if(pre) (ans*=2)%=mod;
            }
            i++;
        }
        else{
            if(i==0) (ans*=6)%=mod;
            else{
                if(pre) (ans*=2)%=mod;
                else (ans*=3)%=mod;
            }
            i+=2;
        }
        pre=now;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <climits>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
#include <stack>

using namespace std;

int main(void){

    int N;
    cin >> N;

    cout << (N+1)/2 << endl;
    return 0;
}


Measured memory_bytes: 256
s = input()

if s[0] == 'R' and s[1] == 'R' and s[2] == 'R':
    print(3)
elif s[0] == 'R' and s[1] == 'R':
    print(2)
elif s[1] == 'R' and s[2] == 'R':
    print(2)
elif s[0] == 'S' and s[1] == 'S' and s[2] == 'S':
    print(0)
else:
    print(1)

Measured memory_bytes: 9108
#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> Pi;

int N, P[100];
Pi dp[2][501 * 100];
//dpは　枚数　コスト　の順番で持つ
const int INF = 1145141919;

void update(Pi& a, Pi b) {
	if (a.first < b.first)a = b;
	else if (a.first > b.first);
	else {
		if (a.second > b.second)a = b;
	}
}

int main() {
	while (1) {
		cin >> N;
		if (N == 0)break;
		for (int i = 0; i < N; i++)cin >> P[i];

		for (int i = 0; i < 2; i++)for (int j = 0; j <= 500 * 100; j++)dp[i][j] = Pi(0, INF);
		auto now = dp[0], next = dp[1];

		now[0] = Pi(0, 0);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= N * 500; j++) {
				if (now[j] == Pi(0, INF))continue;

				if (1 <= P[i] % 1000 && P[i] % 1000 <= 500) {
					//千円札で払えばかならず１枚手に入る
					update(next[j + 500 - (P[i] % 1000)], Pi(now[j].first + 1, now[j].second + P[i]));
				}
				else if (P[i] % 1000 == 0) {
					//何もしない
					next[j] = now[j];

					//1000円札＋小銭で、五百円玉がおつりででるように払う
					if (j >= 500) {
						update(next[j - 500], Pi(now[j].first + 1, now[j].second + P[i]));
					}

				}
				else {
					//何もしない
					next[j] = now[j];
					//千円札で買って、小銭を増やす
					update(next[j + (1000 - (P[i] % 1000))], Pi(now[j].first, now[j].second + P[i]));

					//小銭を使って、五百円玉がおつりででるように払う
					if (j >= (P[i] % 1000) - 500) {
						update(next[j - (P[i] % 1000 - 500)], Pi(now[j].first + 1, now[j].second + P[i]));
					}
				}

			}
			swap(now, next);
		}

		int coin = 0, cost = 0;
		for (int i = 0; i <= N * 500; i++) {
			if (now[i] != Pi(INF, INF)) {
				if (coin < now[i].first)coin = now[i].first, cost = now[i].second;
				else if (coin == now[i].first && cost > now[i].second)cost = now[i].second;
			}
		}

		cout << coin << " " << cost << endl;

	}
	return 0;
}


Measured memory_bytes: 3896