akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
#define X first
#define Y second

const int N = 305, M = int(1e9) + 7;

int n, m, d[N][N][N];
bool c[N][N][N];
vector<pii> v[N];

int f(int x, int y, int z){
	if(c[x][y][z]) return d[x][y][z];
	c[x][y][z] = 1;
	for(pii i : v[x]){
		if((i.Y == 1 && y < i.X) ||
			(i.Y == 2 && y >= i.X && z < i.X) ||
			(i.Y == 3 && z >= i.X)) continue;
		return 0;
	}
	if(x == n) d[x][y][z] = 1;
	else d[x][y][z] = ((f(x + 1, y, z) + f(x + 1, x, z)) % M + f(x + 1, x, y)) % M;
	return d[x][y][z];
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for(int x, y, z; m--; ){
		cin >> x >> y >> z;
		v[y].emplace_back(x, z);
	}
	cout << (3LL * f(1, 0, 0) % M) << endl;
}

Measured memory_bytes: 135680
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


t=n_in()


def execute(n, memo, setting):
    if n in memo:
        return memo[n]

    res = setting[1]*n
    for k in [2,3,5]:
        if n%k == 0:
            res = min(res, execute(n//k, memo, setting) + setting[k])
        else:            
            down = (n//k)*k
            res = min(res, execute(down//k, memo, setting) + setting[k] + (n-down)*setting[1])
            up = (n//k)*k+k
            res = min(res, execute(up//k, memo, setting) + setting[k] + (up-n)*setting[1])

    memo[n] = res
    return res

    

for _ in range(t):
    n,a,b,c,d = l_in()

    setting={2: a, 3: b, 5: c, 1: d}
    memo={1: d, 0: 0}

    print(execute(n,memo,setting))
    


Measured memory_bytes: 93276
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
 
  int s;
  cin >> s;
  vector<int> dp(s+1);
  int mod = 1e9+7;
  dp[0] = 1;
  for(int i=0; i<=s; i++){
    for(int j=3; j+i <= s; j++){
      dp[j+i] += dp[i];
      dp[j+i] %= mod;
    }
  }
  cout << dp[s];
  
  return 0;
}

Measured memory_bytes: 3648
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 5e3 + 5;
LL f[maxn], mn, ans;
int a[maxn], n, A, B, pos[maxn];
int main() {
	scanf("%d%d%d", &n, &A, &B);
	for(register int i = 1; i <= n; ++i) 
		scanf("%d", &a[i]), pos[a[i]] = i;
	memset(f, 0x3f, sizeof(f)), f[0] = 0;
	ans = 0x3f3f3f3f3f3f3f3f;
	for(register int i = 1; i <= n; ++i) {
		mn = 0x3f3f3f3f3f3f3f3f;
		for(register int j = 0; j <= n; ++j) {
			mn = min(mn, f[j]);
			if(pos[i] < j) f[j] = mn + A;
			else if(pos[i] > j) f[j] = mn + B;
			else f[j] = mn;
		}
	}
	for(register int i = 1; i <= n; ++i)
		ans = min(f[i], ans);
	printf("%lld", ans);
	return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int d = sc.nextInt();
		int x = sc.nextInt();
		int tmp = x;
		for(int i = 1; i <= 10; i++) {
			tmp = r*tmp - d;
			System.out.println(tmp);
		}
		
		sc.close();
	}
}


Measured memory_bytes: 23124
import re
a,b = list(map(int,input().split()))
s = input()
if re.search(r"[0-9][0-9]*",s[0:a]):
  if s[a]=="-":
    if re.search(r"[0-9][0-9]*",s[(a+1):]):
      print("Yes")
      exit()
print("No")

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

int main() {
  int a[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1};
  int n, s, e, p;

  cin >> n;
  for (int i=0; i<n; i++) {
    cin >> s >> e;
    if (!s || s > 5 || s < e) {
      p = s;
    } else {
      p = 15-s;
    }
    while (a[p]!=e) {
      cout << a[p] << " ";
      p = (p+1)%15;
    }
    cout << a[p] << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

dp = [0 for k in range(w+1)]
used = [[0 for i in range(n)] for k in range(w+1)]

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0 and i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda

#print(used)
print(max(dp))


Measured memory_bytes: 178268
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	int a,b,h,m; cin >> a >> b >> h >> m;
	double dis = h * 30;
	dis -= (double)m * 5.5;
	if(dis < 0) dis = -dis;
	chmin(dis, 360.0 - dis);
	double ans = a*a + b*b - 2*a*b*cos(dis/(double)180.0*pi);
	printf("%.12f\n",sqrt(ans));
}

Measured memory_bytes: 4228
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
using ll = long long;

int main(){
  ll N;
  cin >> N;
  vector<ll> A(N);
  for( ll i=0; i<N; i++ ) cin >> A.at(i);
  
  ll Sum = 0;
  for( ll i=0; i<N; i++ ) Sum += A.at(i);
  
  vector<ll> x(N);
  ll tmp;
  //for( ll i=0; i<N; i++ ){
  for( ll i=0; i<1; i++ ){  // x[0]だけ求める
    tmp = 0;
    for( ll k=0; k<(N-1)/2; k++ ){
      tmp += A.at((i+1+2*k)%N);
    }
    x.at(i) = Sum/2 - tmp;
  }
  
  for( ll i=1; i<N; i++ ) x.at(i) = A.at(i-1) - x.at(i-1);
  
  for( ll i=0; i<N; i++ ) cout << 2*x.at(i) << " ";
  return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main()
  {int N, C{}; cin >> N;
  for (int i{1}; i <= N; i += 2)
    {int c{}; for (int j{1}; j <= i; ++j) c += !(i % j);
    C += c == 8;}
  cout << C;}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
using namespace std;
const int maxn = 100100;
vector<int>g[maxn];
ll n, mod;
ll dp[maxn];

void dfs_zero(int node, int p) {
	dp[node] = 1LL;
	for(int i:g[node]) {
		if(i == p) continue;
		
		dfs_zero(i, node);
		dp[node] *= (dp[i] + 1)%mod;
		dp[node] %= mod;
	}

}

void dfs_one(int node, int p, ll carry0=1LL) {
	vector<ll>pref(g[node].size()+3);
	vector<ll>suff(g[node].size()+3);
	vector<ll>dps(g[node].size()+3);

	pref[0] = dps[0] = 1LL; // empty node
	int x = 1, br = 0;
	for(int i:g[node]) {
		if(i == p) continue;
		dps[x] = (dp[i] + 1)%mod;
		x++;
		br++;
	}

	dp[node] *= carry0%mod;
	dp[node] %= mod;

	for(int i=1;i<=br;i++) {
		pref[i] = (pref[i-1] * dps[i])%mod;
	}

	suff[br+1] = dps[br+1] = 1LL;
	for(int i=br;i>=0;i--) {
		suff[i] = (suff[i+1] * dps[i])%mod;
	}

	x = 1;
	for(int i:g[node]) {
		if(i == p) continue;

		ll tmp = 1LL * pref[x-1] % mod;
		tmp *= suff[x+1] % mod;
		tmp %= mod;
		tmp *= carry0; tmp %= mod;

		dfs_one(i, node, tmp+1);
		x++;
	}

}

int main() {
	cin>>n>>mod;
	ll a, b;
	for(int i=0;i<n-1;i++) {
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}

	dfs_zero(1, -1);
	dfs_one(1, -1);

	for(int i=1;i<=n;i++) {
		cout<<dp[i]<<"\n";
	}
}

Measured memory_bytes: 24704
#include <cstdio>
#include <queue>

#define H 50
#define W 50

#define INF 10000

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

using namespace std;

int main(void){
  char map[H*W];
  int dist[H*W];
  int h,w, whites = 0;
  queue<int> que;
  
  // read data
  scanf("%d%d", &h, &w);
  for (int i=0; i<h; i++){
    char buf[W];
    scanf("%s", buf);
    for (int j=0; j<w; j++){
      map[j+i*w] = buf[j];
      if (buf[j] == '.') whites++;
      dist[j+i*w] = INF;
    }
  }
  
  // bfs
  que.push(0);
  dist[0] = 0;
  while(!que.empty()){
    int x = que.front() % w;
    int y = que.front() / w;
    que.pop();
    for (int d=0; d<4; d++){
      int xx = x+dx[d], yy = y+dy[d];
      if (xx<0 || xx>=w || yy<0 || yy>=h) continue;
      if (map[xx+yy*w]=='.' && dist[x+y*w]+1 < dist[xx+yy*w]){
        dist[xx+yy*w] = dist[x+y*w] + 1;
//        printf("(%d, %d): %d\n", xx, yy, dist[xx+yy*w]);
        que.push(xx+yy*w);
      }
    }
  }
  
  printf("%d\n", dist[w*h-1]==INF? -1 : whites-dist[w*h-1]-1);
  return 0;
}
  

Measured memory_bytes: 256
def knapsack(items, budget)
    table = (0..1).map{ Array.new(budget+1, 0) }
    for i in 0..items.size-1
        c, v = items[i]
        (0..c-1).each do |j|
            x = table[0][j]
            table[1][j] = x
        end
        (c..budget).each do |j|
            x = table[0][j]
            y = table[0][j-c] + v
            table[1][j] = x > y ? x : y
        end
        table << table.shift
    end
    table[0]
end

c, n, m = gets.split.map(&:to_i)
a = (1..n).map { gets.split.map(&:to_i) }
t = knapsack(a.map {|s, p| [s, p]}, c)
(1..m).each do |k|
    p t[c / k] * k
end




Measured memory_bytes: 9864
import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.util.*;
import java.io.*;

public class Main {

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String t = sc.next();
		int cnt = 0;
		for(int i=0;i<n;i++) {
			String s = sc.next();
			for(int j=0;j<s.length();j++) if( t.charAt(0) == s.charAt(j) ) {
				boolean f = false;
				for(int k=1;k<=s.length();k++) {
					int pt = 0, ps = j;
					while(pt < t.length() && ps < s.length() && t.charAt(pt) == s.charAt(ps)) {
//						debug("", i, pt, ps, k);
						pt++; ps+=k;
					}
					if(pt == t.length()) {
//						debug(i, k, j);
						f = true;
						break;
					}
				}
				if(f) {
					cnt++;
					break;
				}
			}
		}
		System.out.println(cnt);
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 20888
x1, y1, x2, y2 = map(int, input().split())

ll = (x2-x1)**2 + (y2-y1)**2
if (x1>=x2):
    if (y1>=y2):
        l=x1-x2
        s=y1-y2
        x3=x2+s
        x4=x1+s
        y3=y2-l
        y4=y1-l
    else:
        l=y2-y1
        s=x1-x2
        x3=x2-l
        x4=x1-l
        y3=y2-s
        y4=y1-s
else:
    if (y1<=y2):
        l=x2-x1
        s=y2-y1
        x3=x2-s
        x4=x1-s
        y3=y2+l
        y4=y1+l
    else:
        l=y1-y2
        s=x2-x1
        x3=x2+l
        x4=x1+l
        y3=y2+s
        y4=y1+s
        


print(x3, y3, x4, y4)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
LL n;
char s[11],s2[11]; 
int main()
{
    cin >> n;
    for (int i = sqrt(n); i >= 1; -- i) 
    {
        if (n % i == 0)
        {
            int i2 = n / i; 
            sprintf(s,"%d",i);
            sprintf(s2,"%d",i2);
            cout << max(strlen(s),strlen(s2)) << endl; 
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
N, M, X = map(int, input().split())
books = [tuple(map(int, input().split())) for _ in range(N)]
MAX = 10**12
ans = MAX
for bit in range(1 << N):
    money = 0
    algo = [0] * M
    for i in range(N):
        if ((bit >> i) & 1) == 1:
            C, *A, = books[i]
            money += C
            for j, a in enumerate(A): algo[j] += a
    if any(a < X for a in algo): continue
    ans = min(ans, money)
print(ans if ans != MAX else -1)

Measured memory_bytes: 9216
n ,d = map(int, input().split())
count = 0
count2 = 0

for i in range(1, n+1):
    if count == 0:
        if i - d == 1:
            count += 1
    else:
        count2 += 1
        if count2 == d*2+1:
            count += 1
            count2 = 0

if count2 >= d+1:
  count += 1
if n <= d:
  count += 1

print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

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

    deque<char> dq(begin(s), end(s));
    lint ans = 0;
    while(dq.size() >= 2) {
        if(dq.front() == dq.back()) {
            dq.pop_front();
            dq.pop_back();
        } else if(dq.front() == 'x') {
            dq.pop_front();
            ans++;
        } else if(dq.back() == 'x') {
            dq.pop_back();
            ans++;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
import sys
import math
import itertools
import collections

def solve(A,B,C,K):
    ans = 0
    while K != 0:
        if( A != 0):
            if(K < A):
                ans += K
                break
            else:
                ans+=A
                K -= A
                A = 0
        elif(B != 0):
            if(K < B):
                break
            else:
                K -= B
                B = 0
        else:
            if(K < C):
                ans -= K
                break
            else:
                ans -= C
                K -= C
                C = 0
    return ans
def main():
    A,B,C,K =map(int,input().split())
    # solve()
    print(solve(A,B,C,K))

if __name__ == "__main__":
    main()


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

int main(){
    int n;
    cin >> n;
    int a;
    map<int,int> m;
    for(int i=0;i<n;i++){
        cin >> a;
        m[a]++;
    }
    if(m.size()==n){
        cout << "YES" << endl;
    }else{
        cout <<"NO"<<endl;
    }
}

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

int main(){
    int n;
    cin >> n;
    vector<pair<int, int> > left, right;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        int add=0, maxdiff=0;
        for(int j=0; j<(int)s.length(); j++){
            if(s[j]=='(') add++;
            else add--;
            maxdiff = max(maxdiff, -add);
        }
        if(add >= 0){
            left.push_back(make_pair(maxdiff, add));
        }else{
            int add=0, maxdiff=0;
            for(int j=s.length()-1; j>=0; j--){
                if(s[j]==')') add++;
                else add--;
                maxdiff = max(maxdiff, -add);
            }
            right.push_back(make_pair(maxdiff, add));
        }
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    int depthl=0;
    bool success = true;
    for(int i=0; i<(int)left.size(); i++){
        if(left[i].first > depthl) success = false;
        depthl += left[i].second;
    }
    int depthr=0;
    for(int i=0; i<(int)right.size(); i++){
        if(right[i].first > depthr) success = false;
        depthr += right[i].second;
    }
    if(depthl != depthr) success = false;
    if(success){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 3208
n = int(input())
s = []
for i in range(n):
    s.append(input())
m = int(input())
t = []
for i in range(m):
    t.append(input())

words = set(s + t)
max_val = 0
for word in words:
    ans = s.count(word)
    ans -= t.count(word)
    if ans > max_val:
        max_val = ans
print(max_val) 

Measured memory_bytes: 9160
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    w,h,x,y,r=map(int,input().split())
    if all(0<=x+s<=w and 0<=y+t<=h for s,t in ((-r,0),(r,0),(0,r),(0,-r))):
        print("Yes")
    else:
        print("No")
if __name__ == '__main__':
    main()


Measured memory_bytes: 6904
#include <iostream>
#include <string>

using namespace std;

string s;
string b="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n,i;
int main()
{
    cin>>n>>s;
    for(i=0;i<s.size();i++){
        s[i]=b[(s[i]-'A'+n)%26];
    }
    cout<<s;
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        FastScanner fs=new FastScanner();
        int n=fs.nextInt();
        int m=fs.nextInt();
        HashMap<Integer, HashSet<Integer>>map=new HashMap<Integer, HashSet<Integer>>();
        for(int i=1;i<=n;i++)map.put(i,new HashSet<>());
        for (int tt=0; tt<m; tt++){
            int a=fs.nextInt();
            int b=fs.nextInt();
            map.get(a).add(b);
            map.get(b).add(a);
        }
        int max = 0;
        
        Set<Integer> seen = new HashSet<Integer>();
        for(int j = 1;j<=n;j++){

            if (!seen.contains(j)){

                Stack<Integer> dfs = new Stack<Integer>();
                dfs.add(j);
                Set<Integer> tempseen = new HashSet<Integer>();
                while(!dfs.isEmpty()){
                    int vertex = dfs.pop();
                    for(int child : map.get(vertex)){
                        if (!tempseen.contains(child))
                            dfs.add(child);
                    }
                    tempseen.add(vertex);
                    seen.add(vertex);
                }
                max=Math.max(tempseen.size(), max);
            }

        }
        System.out.println(max);



    }
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}


Measured memory_bytes: 168640
#include <cstdio>
#include <cstring>

const int N = 2e5 + 5;

char s[N];

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1), cnt = 0;
	long long ans = 0;
	for (int i = 1; i <= n - 2; i++) {
		if (s[i] == 'A') {
			if (s[i + 1] == 'B' && s[i + 2] == 'C') {
				ans += cnt + 1, s[i + 2] = 'A', i++;
			} else {
				cnt++;
			}
		} else {
			cnt = 0;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] an = ReadInts();
            int sa = an[1] - an[0];
            int a = sa * (sa + 1) / 2;
            WriteLine(a - an[1]);
        }


        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }


    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <vector>

int main() {
  int n, k, c;
  std::string s;
  std::cin >> n >> k >> c >> s;
  std::vector<int> left(k), right(k);
  int pos = 0;
  for (int i = 0; i < k; i++) {
    while (pos < n && s[pos] == 'x') pos++;
    left[i] = pos;
    pos += c + 1;
  }
  pos = n - 1;
  for (int i = 0; i < k; i++) {
    while (pos >= 0 && s[pos] == 'x') pos--;
    right[k - i - 1] = pos;
    pos -= c + 1;
  }
  for (int i = 0; i < k; i++) std::cerr << left[i] << " \n"[i == k - 1];
  for (int i = 0; i < k; i++) std::cerr << right[i] << " \n"[i == k - 1];
  for (int i = 0; i < k; i++) 
    if (left[i] == right[i])
      std::cout << left[i] + 1 << std::endl;
  return 0;
}

Measured memory_bytes: 3332
#include<bits/stdc++.h>
using namespace std;
const int N=402,M=100002;
int n,m,i,j,ans,x[M],y[M],k;
bool vis[N],mp[N][N],fl;
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
	for (i=1;i<=n;i++){
		mp[i][i]=1;
		for (j=m;j;j--){
			bool &xx=mp[i][x[j]],&yy=mp[i][y[j]];
			if (xx && yy){
				vis[i]=1;
				break;
			}else if (xx) yy=1;
			else if (yy) xx=1;
		}
	}
	for (i=1;i<=n;i++) if (!vis[i])
		for (j=i+1;j<=n;j++) if (!vis[j] && !mp[i][j]){
			fl=1;
			for (k=1;k<=n;k++)
				if (mp[i][k] && mp[j][k]) fl=0;
			ans+=fl;
		}
	printf("%d",ans);
}


Measured memory_bytes: 1152
void main() {
	auto ip = readAs!(int[]), H = ip[0], W = ip[1];
	auto C = readMatrix!char(H, W);
	foreach(i; C) foreach(_; 0..2) i.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,k,s;
    scanf("%d%d%d",&n,&k,&s);
    if(s>10000000){
        if(k==0){
            printf("%d",s/2+1);
            for(int i=1;i<n;i++)
                printf(" %d",s/2+1);
        }else{
            printf("%d",s);
            for(int i=1;i<k;i++)
                printf(" %d",s);
            for(int i=0;i<n-k;i++)
                printf(" %d",s/2+1);
        }
    }else{
        if(k==0){
            printf("%d",s+1);
            for(int i=1;i<n;i++)
                printf(" %d",s+1);
        }else{
            printf("%d",s);
            for(int i=1;i<k;i++)
                printf(" %d",s);
            for(int i=0;i<n-k;i++)
                printf(" %d",s+1);
        }
    }
    return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;
int main(){
  int n, m;
  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    int a[n], b[m];
    int suma = 0, sumb = 0;
    for(int i = 0 ; i < n ; i++){
      cin >> a[i];
    }
    for(int i = 0 ; i < m ; i++){
      cin >> b[i];
    }
    
    bool flag = 0;
    int x, y;
    
    for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < m ; j++){
	swap(a[i], b[j]);
	x = a[i], y = b[j];
	suma = accumulate(a, a+n, 0);
	sumb = accumulate(b, b+m, 0);
	//printf("suma = %d, sumb = %d\n", suma, sumb);
	if(suma == sumb){
	  printf("%d %d\n", y, x);
	  flag = 1;
	  break;
	}
	else swap(a[i], b[j]);
      }
      if(flag == 1) break;
    }
    if(flag == 0) cout << -1 << endl;
  }
  return 0;
}

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

int arr[200000], height[200000];

struct node
{
    int l, r;
    long long val;
    node *lnode, *rnode;
    
    node(int L, int R)
    {
        l = L;
        r = R;
        val = 0;
        
        if (r - l != 1)
        {
            lnode = new node(l, l + r >> 1);
            rnode = new node(l + r >> 1, r);
        }
    }
    
    long long query(int L, int R)
    {
        if (L >= r || l >= R) return 0;
        if (L <= l && r <= R) return val;
        
        return max(lnode->query(L, R), rnode->query(L, R));
    }
    
    void update(int i, long long v)
    {
        if (i >= r || l >= i + 1) return;
        if (r - l == 1) 
        {
            val = v;
            return;
        }
        
        lnode->update(i, v);
        rnode->update(i, v);
        val = max(lnode->val, rnode->val);
    }
};

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i != n; ++i)
        scanf("%d", &height[i]);
    for (int i = 0; i != n; ++i)
        scanf("%d", &arr[i]);
    
    node *st = new node(0, n);
    
    long long ans = 0;
    
    for (int i = 0; i != n; ++i)
    {
        long long tmp = st->query(0, height[i]) + arr[i];
        ans = max(ans, tmp);
        st->update(height[i], tmp);
    }
    
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 20608
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

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


Measured memory_bytes: 256
n,w=map(int,input().split())
inf=float('inf')

dp=[inf]*100001
dp[0]=0


for i in range(0,n):
    nextdp=[inf]*100001
    x=[int(i) for i in input().split()]
    for j in range(100001):
        if x[1] <= j:
            nextdp[j]=min(dp[j],x[0]+dp[j-x[1]])
        else:
            nextdp[j]=dp[j]
    dp=nextdp


for i in range(100000,-1,-1):
    if dp[i]<=w:
        print(i)
        break


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

int main() {
  int N, K; cin >> N >> K;
  vector<int> x(N);
  for (int i = 0; i < N; i++) cin >> x.at(i);
  int dis = 1000000000;
  for (int i = 0; i <= N-K; i++) {
    int root1 = abs(x.at(i)) + (x.at(i+K-1) - x.at(i));
    int root2 = abs(x.at(i+K-1)) + (x.at(i+K-1) - x.at(i));
    if (min(root1, root2) < dis) dis = min(root1, root2);
  }
  cout << dis << endl;
}


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

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
s = [(K - 1, 0)]
while s:
  v, c = s.pop()
  D[v] = c
  for vv, cc in G[v]:
    if D[vv] < 0:
      s.append((vv, cc + c))
  
for x, y in XY:
  print(D[x - 1] + D[y - 1])

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

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

  int P[N];
  for(int i = 0; i < N; ++i) cin >> P[i];

  int f = count_if(P, P+N, [&A](int x){ return x <= A; });
  int s = count_if(P, P+N, [&A, &B](int x){ return x > A && x <= B; });
  int t = count_if(P, P+N, [&B](int x){ return x > B; });

  cout << min(f, min(s, t)) << endl;
}

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

const long long N = 3e6 + 17;
ll a[N], b[N], cnt, ans, lnt, n, m, r1, r0, l1, l0, sum, mx, h, c[N], t[N], mn = N, x, y, k;
pair<ll,ll>pr[N];
vector<ll>v,v2;
map<ll,ll>mp;
bool used[N];
char ch[N];
ll prime[N] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
   cin >> n >> m;
   cout << (n - 1) * (m - 1);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }



int main(void){
    // Your code here!
    int n,M ;
    cin >> n >> M ;
    vector<int> a(n+1,0);
    vector<int> b(n+1,0);
    FOR(i,1,n) cin >> a.at(i) >> b.at(i) ;
    vector<vector<int>> q(100005);
    FOR(i,i,n) q.at(a.at(i)).push_back(b.at(i));

    priority_queue<int> que;
    int ans = 0;
    FOR(m,1,M) {
        for (auto &x:q.at(m)){
            que.push(x);
        };
        if (!que.empty()) {
            ans += que.top();
            que.pop();
        }
    }
    cout << ans << endl;
}

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

int main()
{
    string s;
    getline(cin,s);
    for(int i=0; i<s.size(); i++)
    {
        if(s[5]==',')
            s[5]=' ';
        if(s[13]==',')
            s[13]=' ';

    }
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    set<string> used;
    printf("?aaaaa\n");
    fflush(stdout);

    int i = 0;
    for(;;){
        string s;
        cin >> s;
        if(s[0] != 'a' || used.find(s) != used.end()){
            cout << "!OUT" << endl;
            return 0;
        }
        used.insert(s);

        s = s[s.size()-1];
        if(i == 26)
            s += "aa";
        else
            s += 'a' + i;
        s += 'a';
        ++ i;

        printf("?%s\n", s.c_str());
        fflush(stdout);
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong x;
llong ans;

int main() {
    cin >> x;

    ans += 1000 * (x / 500);
    x %= 500;
    ans += 5 * (x / 5);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
//const int MOD = 1e9 + 7;

int main(){
	int n;
	cin >> n;
	vector<int> l(n);
	rep(i,n) cin >> l[i];
	sort(l.begin(), l.end());
	
	int res = 0;
	rep(i,n){
		for(int j = i+1; j < n; j++){
			int a = l[i];
			int b = l[j];
			res += lower_bound( l.begin(), l.end(), a+b) - l.begin() - (j+1);
			//cout << i << " " << j << " " << res << endl;
		}
	}
	
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int arr[1010];
int main()
{
    int n,i,j,k,x,y,ans,curr,m;
    int tc;
    cin >> n >> k;
    for(i=1;i<=n;i++) {
        cin >> arr[i];
    }
    sort(arr+1, arr+n+1);
    int chaeng = 0;
    for(i=1;i<=k;i++) chaeng += arr[i];
    cout << chaeng << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    string s;
    cin >> s;

    int64_t m = s.size();

    vector a(1, 0L);
    int64_t t = 0;
    for (auto c : s) {
        if (c == '0') {
            a.push_back(t);
        } else {
            ++t;
        }
    }
    a.push_back(t);

    int64_t k;
    cin >> k;
    k = min(k, a.back());

    int64_t n = a.size();

    constexpr auto M = 998244353L;

    vector dp(2, vector(k + 1, vector(a.back() + 1, 0L)));
    int64_t h = 0, mk = 0;
    dp[h][0][0] = 1;
    for (auto i : irange(0L, n - 1)) {
        auto&& prev = dp[h];
        auto&& next = dp[!h];
        h = !h;

        for (auto j : irange(mk, -1L, -1L)) {
            int64_t ss = 0;
            for (auto c : irange(a[i + 1], a.back() + 1)) {
                next[j][c] = ss + prev[j][a[i] + (c - a[i + 1])];
                if (next[j][c] >= M) {
                    next[j][c] -= M;
                }
                ss += prev[j][a[i] + (c - a[i + 1])];
                if (ss >= M) {
                    ss -= M;
                }
            }

            for (auto c : irange(a[i + 1], a.back() + 1)) {
                for (auto b : irange(a[i] + (c - a[i + 1]) + 1, c + 1)) {
                    auto w = j + b - (a[i] + (c - a[i + 1]));
                    if (w > k) {
                        break;
                    }
                    mk = max(mk, w);
                    next[w][c] += prev[j][b];
                    if (next[w][c] >= M) {
                        next[w][c] -= M;
                    }
                }
            }
        }
    }

    int64_t ans = 0;
    for (auto i : irange(0L, k + 1)) {
        ans += dp[h][i][a.back()];
        if (ans >= M) {
            ans -= M;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 5088
#include <bits/stdc++.h>
using namespace std;
using ld = long double;

int main()
{
	cout << fixed << setprecision(10);
	int N, K;
	cin >> N >> K;
	vector<ld> dp(K);
	for (int i = K - 1; i >= 0; i--) {
		dp[i] = i * 2 >= K ? 0.5 : dp[i * 2] * 0.5;
	}
	ld res = 0;
	for (int i = 1; i <= N; i++) {
		res += (i < K ? dp[i] : 1.0) / N;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
long long a[1000000];
long long suf[1000000];
long long pre[1000000];
int cur=1;
long long L;
long long R;
void Advance()
{
    L+=a[cur+1];
    R-=a[cur+1];
    cur++;
}
void Retreat()
{
    L-=a[cur];
    R+=a[cur];
    cur--;
}
void Advance2()
{
    L+=a[cur-1];
    R-=a[cur-1];
    cur--;
}
void Retreat2()
{
    L-=a[cur];
    R+=a[cur];
    cur++;
}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    L=a[1];
    R=0;
    for (int i=2;i<=n;i++)
    {
        R+=a[i];
        long long best = abs(R-L);
        int id = cur;
        while(cur+1<i && L<R)
        {
            Advance();
            if (abs(R-L)<best)best=abs(R-L),id=cur;
        }
        if (cur!=1)
        {
            Retreat();
            if (abs(R-L)<best)best=abs(R-L),id=cur;
        }
        pre[i]=id;
    }
    L=a[n];
    R=0;
    cur = n;
    for (int i=n-1;i>=1;i--)
    {
        R+=a[i];
        long long best = abs(R-L);
        int id = cur;
        while(cur-1>i && L<R)
        {
            Advance2();
            if (abs(R-L)<best)best=abs(R-L),id=cur;
        }
        if (cur!=n)
        {
            Retreat2();
            if (abs(R-L)<best)best=abs(R-L),id=cur;
        }
        suf[i]=id;
    }
    /*for (int i=1;i<=n;i++)
        cout<<pre[i]<<' ';
    cout<<endl;
    for (int i=1;i<=n;i++)
        cout<<suf[i]<<' ';
    cout<<endl;*/
    for (int i=1;i<=n;i++)
        a[i]=a[i-1]+a[i];
    long long ret= 1e18;
    for (int i=2;i<=n-2;i++)
    {
        int b1 = pre[i];
        int b2 = suf[i+1];
        long long mn = min(min(a[b1],a[i]-a[b1]),min(a[n]-a[b2-1],a[b2-1]-a[i]));
        long long mx = max(max(a[b1],a[i]-a[b1]),max(a[n]-a[b2-1],a[b2-1]-a[i]));
        ret = min(ret,mx-mn);
    }
    cout<<ret<<endl;
}


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

int main() {

  vector<queue<char>> v(3);
  string s;

  rep(i, 0, 3) {
    cin >> s;
    for (char c : s) {
      v[i].push(c);
    }
  }

  int tmp, x = 0;

  while (true) {
    if (v[x].empty()) {
      break;
    }
    tmp = x;
    x = v[x].front() - 'a';
    v[tmp].pop();
  }

  cout << char(x + 'A') << endl;
  getchar();
}

Measured memory_bytes: 3592
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		String s = in.next();
		int[] a = new int[10];
		for (int i=0; i<10; i++) {
			a[i] = s.charAt(i) - '0';
		}

		int size = 10;
		for (int i=0; i<10; i++) {
			for (int j=0; j<size-1; j++) {
				a[j] = (a[j] + a[j+1])%10;
			}
			size--;
		}

		out.println(a[0]);
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		while(in.hasNext()) solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26212
#include <stdio.h>
#include <string.h>
#define REP(i,a,b) for (i=(a); i<(b); ++i)
#define rep(i,n) REP(i,0,n)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
double a[101][101];
double memo[101][101][101];

double solve(int n, int m, int k, int p)
{
    double res;
    int i, j;
    if (m == 1) return 1;
    if (memo[p][m][k] > 0) return memo[p][m][k];
    res = 0;
    rep(i, n) res = MAX(res, solve(n, m-1, p, i) * a[p][i]);
    return memo[p][m][k] = res;
}

int main(void)
{
    int n, m, i, j, k;
    double res;
    while (scanf("%d%d",&n,&m),n|m) {
        memset(memo, 0, sizeof(memo));
        rep(i, n) rep(j, n) scanf("%lf", &a[i][j]);
        res = 0;
        rep(i, n) rep(j, n) res = MAX(res, solve(n, m, i, j));
        printf("%.2f\n", res);
    }

    return 0;
}

Measured memory_bytes: 8600
let n = read_int ()
let m = int_of_float (10. ** 9. +. 7.)

let fact n =
  let rec f i n' = 
    if i = 1 then n' mod m else f (i - 1) (i mod m * n' mod m)
  in 
  f n 1

let () = Printf.printf "%d\n" (fact n)

Measured memory_bytes: 384
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<limits>
#include<stack>

using namespace std;

typedef unsigned long long ll;
typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;

int INF = std::numeric_limits<int>::max();
int NINF = std::numeric_limits<int>::min();
int MOD = 1e9+7;

int col[] = {0,-1,0,1,1,1,-1,-1};
int row[] = {-1,0,1,0,1,-1,1,-1};

//knight moves
int cc[] = {1,2,2,1,-1,-1,-2,-2};
int rr[] = {-2,-1,1,2,-2,2,1,-1};

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

    int n, w;
    cin >> n >> w;

    vi wts(n), vals(n);
    vvll dp(n,vll(w+1,0));

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

    //initialize dp table
    for(int i = wts[0]; i <= w ; ++i)
        dp[0][i] = vals[0];

    for(int i = 1 ; i < n; ++i)
    {
        for(int j = 0; j < wts[i] ; ++j)
            dp[i][j] = dp[i-1][j];

        for(int j = wts[i]; j <= w ; ++j)
        {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wts[i]] +vals[i]);
        }
    }

     /*for(int i = 0 ; i < n; ++i)
    {
        for(int j = 0; j <= w ; ++j)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/

    cout << dp[n-1][w];
    return 0;
}


Measured memory_bytes: 82268
h,w=map(int,input().split())
a=[[j for j in input()] for i in range(h)]
for i in range(h):
  if a[i].count('.')==w:
    a[i]=[]
while [] in a:
  a.remove([])
for i in range(w):
  c=0
  for j in range(len(a)):
    if a[j][i]=='.':
      c+=1
  if c==len(a):
    for j in range(len(a)):
      a[j][i]='!'
for i in range(len(a)):
  while '!' in a[i]:
    a[i].remove('!')
for i in a:
  print(*i,sep='')

Measured memory_bytes: 4596
from collections import defaultdict

n = int(input())
A = list(map(int, input().split()))

D = defaultdict(lambda: 0)
for a in A:
    D[a] += 1

ans = 0
for a in A:
    ans = max(
        ans,
        D[a - 2] + D[a - 1] + D[a],
        D[a - 1] + D[a] + D[a + 1],
        D[a] + D[a + 1] + D[a + 2],
    )
print(ans)


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

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> a(41);
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		for (int j = 0; j < 41; j++) {
			a[j] += (x >> j) & 1;
		}
	}
	long long ans = 0;
	for (int i = 0; i < 41; i++) {
		if ((k >> i) & 1) {
			ans += (n - a[i]) * (1LL << i);
		} else {
			ans += a[i] * (1LL << i);
		}
	}
	for (int i = 0; i < 41; i++) {
		if (((k >> i) & 1) == 0) continue;
		long long tmp = 0;
		for (int j = 0; j < i; j++) {
			tmp += max(a[j], n - a[j]) * (1LL << j);
		}
		tmp += a[i] * (1LL << i);
		for (int j = i + 1; j < 41; j++) {
			if ((k >> j) & 1) {
				tmp += (n - a[j]) * (1LL << j);
			} else {
				tmp += a[j] * (1LL << j);
			}
		}
		ans = max(ans, tmp);
	}
	cout << ans << endl;
	return 0;
	}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long x[100010],y[100010],p[100010];
long long q[100010];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  long long a,b,c,d,e,n,ccnt=0,ans=0;
  string s,v,o;
  char z[100010],y[100010];

  cin>>a>>b;
  if(a<b) swap(a,b);
  if(a>=b+2){
    cout<<a+(a-1)<<'\n';
  }else{
    cout<<a+b<<'\n';
  }
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String s = line.replaceAll(" ", "");
        int i = Integer.parseInt(s);
        if (i % 4 == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 21332
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<cmath>
#include<stdlib.h>

using namespace std;

vector<int> jans,ajans,ijans;

string tost(int num,int len);

int main(){
	while(1){
		string num;
		int l;
		
		cin >> num >> l;
		if(num == "0" && l == 0) break;
		int ind = 0;
		map<int,int> nin;
		nin[atoi(num.c_str())] = ind;
		ind++;
		
		while(1){
			map<int,int> nmp;
			for(int i = 0;i < 10;i++){
				nmp[i] = 0;
			}
			int dif = l - num.size();
			for(int i = 0;i < num.size();i++){
				int tn = num[i] - '0';
				nmp[tn]++;
			}
			if(dif > 0)nmp[0] += dif;
			
			string nmx,nmn;
			for(int i = 0;i < 10;i++){
				for(int j = 0;j < nmp[i];j++){
					string ts(1,'0' + i);
					nmn += ts;
				}
			}
			
			for(int i = 9;i >= 0;i--){
				for(int j = 0;j < nmp[i];j++){
					string ts(1,'0' + i);
					nmx += ts;
				}
			}
			
			int tnum = atoi(nmx.c_str()) - atoi(nmn.c_str());
			map<int,int>::iterator it = nin.find(tnum);
			if(it != nin.end()){
				jans.push_back(nin[tnum]);
				ajans.push_back(tnum);
				ijans.push_back(ind - nin[tnum]);
				break;
			}else{
				num = tost(tnum,l);
				nin[tnum] = ind;
				ind++;
			}
		}
	}
	for(int i = 0;i < jans.size();i++) cout << jans[i] << " " << ajans[i] << " " << ijans[i] << endl;
	
	return 0;
}

string tost(int num,int len){
	string snum;
	for(int i = len - 1;i >= 0;i--){
		string st(1,'0' + (int)(num / (int)pow(10.,i)) % 10);
		snum += st;
	}
	return snum;
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  int n,a,b;
  cin>>n>>a>>b;
  vector<int> x(3,0);
  rep(i,n){
    int d;
    cin>>d;
    if(d <= a) x[0]++;
    else if(d <= b) x[1]++;
    else x[2]++;
  }
  cout << *min_element(all(x)) << endl;
  return 0;
}


Measured memory_bytes: 256