akhauriyash/Code-Regression huggingface dataset:
def main():
    S = input()
    x = []
    op = ['+', '-']
    for i in range(2):
        for j in range(2):
            for k in range(2):
                s = op[i] + op[j] + op[k]
                x.append(s)
    # print(x)
    for xi in x:
        st = S[0] + xi[0] + S[1] + xi[1] + S[2] + xi[2] + S[3]
        ans = eval(st)
        # print(ans)
        if ans == 7:
            print(st+'=7')
            break

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
S = input()
S_len = len(S)
import re

S_check = []
a = []
b = []
if S[0] == 'A':
    for i in range(2,S_len-1):
        if S[i] == 'C':
            S_check.append('a')
    if len(S_check) == 1:
        S_list = list(S)
        S_list[0] = str('a')
        C_loc = S.find('C')
        S_list[C_loc] = str('c')
        S = "".join(S_list)
        if S.islower() == True:
            print('AC')
        else:
            print('WA')
    else:
        print('WA')
else:
    print('WA')

 

Measured memory_bytes: 3188
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int h,w,n,ans[111][111];
vector<pii> all;
int main()
{
	get3(h,w,n);
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(i%2)all.pb(mp(i,j));
			else all.pb(mp(i,w-j+1));
		}
	}
	int cur=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		get1(x);
		while(x--)
		{
			ans[all[cur].ff][all[cur].ss]=i;
			cur++;
		}
	}
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)
	{
		printf("%d ",ans[i][j]);
		if(j==w)puts("");
	}
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n],c[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  c[0]=0;
  c[1]=abs(a[1]-a[0]);
  for(int i=2;i<n;i++)
  {
    c[i]=min(c[i-2]+abs(a[i]-a[i-2]), c[i-1]+abs(a[i-1]-a[i]));
  }
  cout<<c[n-1]<<endl;
//   for(int i=0;i<n;i++)
//   cout<<c[i]<<" ";
}

Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

char now[10];
vector <pair<int, string>> ans;

int Addition(int dig){
  string S = "";
  for (int i = 0; i <= dig; i++){
    S += now[i];
  }
  ans.push_back(make_pair(dig, S));
  return 0;
}

int DFS(int turn){
  if (turn == 10) return 0;
  if (turn == 0){
    for (char i = '1'; i <= '9'; i++){
      now[turn] = i;
      Addition(turn);
      DFS(turn + 1);
    }
    return 0;
  }

  for (int i = -1; i < 2; i++){
    char next = now[turn - 1] + i;
    if ('0' <= next && next <= '9'){
      now[turn] = next;
      Addition(turn);
      DFS(turn + 1);
    }
  }
  return 0;
}

int main(){
  DFS(0);
  sort(ans.begin(), ans.end());
  int N; cin >> N;
  cout << ans[N - 1].second << endl;

  return 0;
}


Measured memory_bytes: 16236
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int main() {
	int n;
	cin >> n;
	vector<int>b;
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		if (i % 2 == 0) {
			b.push_back(a);
		}
		else {
			b.insert(b.begin(),a);
		}
	}
	if (n % 2 == 0) {
		for (int i = 0; i < n; ++i) {
			cout << b[i] << " ";
		}
	}
	else {
		reverse(b.begin(), b.end());
		for (int i = 0; i < n; ++i) {
			cout << b[i] << " ";
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3060
/*
	  Author : @evenbao
	  Created : 2020 / 07 / 26
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define pii pair<int , int>
#define mp make_pair
#define fi first
#define se second

const int N = 1 << 18 , L = 1e5 + 10 , B = 512;

int n;
int v[N] , w[N];
LL dp[B][L];

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void read(T &x) {
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

inline LL solve(int u , int l) {
		if (l <= 0) return 0LL;
		if (u < B) return dp[u][l];
		LL ans = solve(u / 2 , l);
		if (l >= w[u]) chkmax(ans , solve(u >> 1 , l - w[u]) + v[u]);
		return ans;
}

int main() {
		
		read(n);
		for (int i = 1; i <= n; ++i) {
				read(v[i]);
				read(w[i]);
		}
		for (int i = 1; i < B; ++i) {
				memcpy(dp[i] , dp[i / 2] , sizeof(dp[i]));
				for (int j = L; j >= w[i]; --j)
						chkmax(dp[i][j] , dp[i][j - w[i]] + v[i]);
		}
		int q; read(q);
		while (q--) {
				int u , l;
				read(u) , read(l);
				printf("%lld\n" , solve(u , l));
		}
	  return 0;
}



Measured memory_bytes: 405108
s = input()

ans = 0
for i in range(2 ** (len(s) - 1)):
    pat = s[0]
    index = 1
    for j in range(len(s) - 1):
        if i >> j & 1:
            pat += "+"
        pat += s[index]
        index += 1
    #print(pat)
    ans += eval(pat)

print(ans)

Measured memory_bytes: 3060
H,W=list(map(int,input().split()))
import numpy as np
m=np.array([[0 if i=="#" else 1 for i in input()] for i in range(H)])
l,r,u,d=np.zeros((4,H,W))
for i in range(H):
   u[i]=(u[i-1]+1)*m[i]
   d[-i-1]=(d[-i]+1)*m[-i-1]
for i in range(W):
   r[:,i]=(r[:,i-1]+1)*m[:,i]
   l[:,-i-1]=(l[:,-i]+1)*m[:,-i-1]
print(int(np.max(u+r+l+d))-3)

Measured memory_bytes: 228824
/* 
    Author : Jeff Ahn
    Sat 27 Jun 2020 04:54:56 AM PDT 
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,r) for(int i = 0; i < (r); i++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define uint unsigned long long
#define endl '\n'

signed main() {
  fastio;
  int a;
  cin >> a;
  int res = 0;
  res = a + a*a + a*a*a;
  cout << res << endl;
}


Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
import sys

N, K = map(int, input().split())
if K == 1:
  print(0)
  sys.exit()
  
if N / K > 1:
  N = N - int(N / K) * K
a = abs(N-K)
while abs(a - K) < a:
  a = abs(a-K)

print(int(a))

Measured memory_bytes: 3060
#include <cstdio>
#include <list>

#define N 100

using namespace std;

/** Crazy Motor-Cycle */
struct cmc
{
  int a;
  int b;
  int c;
};

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  int i;

  for ( ; ; )
  {
    list<struct cmc> lis;
    int d[ 3 * N ];
    int a, b, c;
    int n;

    scanf ( "%d%d%d", &a, &b, &c );
    if ( !( a | b | c ) ) break ;
    b += a; c += b;
    for ( i = 0; i < c; ++i )
    {
      d[ i ] = 2;
    }

    scanf ( "%d", &n );
    while ( n-- )
    {
      struct cmc t;
      int s;

      scanf ( "%d%d%d%d", &t.a, &t.b, &t.c, &s );
      --t.a; --t.b; --t.c;
      if ( s )
      {
        d[ t.a ] =
        d[ t.b ] =
        d[ t.c ] = 1;
      }
      else
      {
        lis.push_back ( t );
      }
    }

    for ( list<struct cmc>::iterator it = lis.begin ( )
        ; it != lis.end ( ); )
    {
      if ( ( d[ it->a ] == 2 && d[ it->b ] == 1 && d[ it->c ] == 1 )
        || ( d[ it->a ] == 1 && d[ it->b ] == 2 && d[ it->c ] == 1 )
        || ( d[ it->a ] == 1 && d[ it->b ] == 1 && d[ it->c ] == 2 ) )
      {
        if      ( d[ it->a ] == 2 ) d[ it->a ]  = 0;
        else if ( d[ it->b ] == 2 ) d[ it->b ]  = 0;
        else                        d[ it->c ]  = 0;
        lis.erase ( it );
        it = lis.begin ( );
      }
      else ++it;
    }

    for ( i = 0; i < c; ++i )
    {
      printf ( "%d\n", d[ i ] );
    }
  }

  return ( 0 );
}

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

namespace Still_TBD
{
    public class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            string[] n = a.Replace("/", " ").Split(' ');
            int[] ymd = n.Select(int.Parse).ToArray();
            Console.WriteLine(Solve(ymd));
        }

        public static string Solve(int[] ymd)
        {
            if (ymd[0] < 2019)
            {
                return "TBD";
            }
            else if (ymd[1] > 4)
            {
                return "TBD";
            }
            else
            {
                return "Heisei";
            }
        }
    }
}


Measured memory_bytes: 13268
import collections
N, M = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(M)]
table = collections.defaultdict(int)
table2 = collections.defaultdict(int)
table2[1] += 1

for i in range(N):
    table[i+1] = 1
reached = [1]
for i in range(M):
    table[xy[i][1]] += 1
    table[xy[i][0]] -= 1
    if xy[i][0] in table2 and table2[xy[i][0]] > 0:
        table2[xy[i][0]] = table[xy[i][0]]
        table2[xy[i][1]] += table[xy[i][1]] + 1

table2 = list(table2.items())
table2 = [x for x in table2 if x[1] > 0]
print(len(table2))


Measured memory_bytes: 50276
m,n=map(int,input().split())
a=list(map(int,input().split()))
if m == 2:
  ans1=0
  for i in range(n):
    if i % 2 != a[i] % 2:
      ans1+=1
  ans2=0
  for i in range(n):
    if i % 2 == a[i] % 2:
      ans2+=1
  print(min(ans1,ans2))
else:
  ans=0
  for i in range(n-1):
    if a[i] == a[i+1]:
      a[i+1]=-1
      ans+=1
  print(ans)


Measured memory_bytes: 16660
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include<cstdio>
#include <vector>
#include<queue>
#include<limits.h>
#include<string.h>
#include<functional>
#include<map>
#include<set>
#include<list>
#include<unordered_map>
#include<queue>
#define P pair<int,int>
using namespace std;

int a[100][100];
bool used[100];
signed main(){
	int b; cin >> b;
	for (int c = 0; c < b; c++) {
		for (int d = 0; d < b; d++) {
			cin >> a[c][d];
			if (a[c][d] == -1) {
				a[c][d] = INT_MAX / 3;
			}
		}
	}
	int ans = 0;
	priority_queue<P,vector<P>, greater<P>>Q;
	Q.push({ 0,0 });
	while (Q.size()) {
		P t = Q.top(); Q.pop();
		if (!used[t.second]) {
			ans += t.first;
			used[t.second] = true;
			for (int i = 0; i < b; i++) {
				Q.push({ a[t.second][i],i });
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
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; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
#define pll pair<ll,ll>
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main(){
    ll n,d,t,s;
    cin>>d>>t>>s;
    if(d<=t*s)cout<<"Yes";
    else cout<<"No";
}




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

using namespace std;

const int N = int(1e2) + 7;
int A[N][N];
int n, d;

void init(){
    scanf("%d %d", &n, &d);
    for(int i = 0; i < n; i++)
        for(int y = 0; y < d; y++)
            scanf("%d", &A[i][y]);
}

void solve(){
    init();
    int ans = 0;
    for(int i = 0; i < n-1; i++)
    for(int y = i+1; y < n; y++){
        int sum = 0;
        for(int q = 0; q < d; q++)
            sum += (A[i][q]-A[y][q])*(A[i][q]-A[y][q]);
        int s = sqrt(sum);
        if(s*s == sum || (s+1)*(s+1) == sum)
            ans++;
    }
    printf("%d\n", ans);

}

const bool mtc = false;

int main(){
    int t;
    if(mtc){
        scanf("%d", &t);
        while(t--) solve();
    }
    else solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
 

int  A(int x){
    if(x>=0)return x;
    else return -x;
}


int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    if(a+b == c || b+c == a || c+a == b){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL

int main()
{
  int x;

  cin >> x;

  cout << 10 - x/200 << endl;

  return 0;
}


Measured memory_bytes: 3580
chomp($x=<>);
$ans=0;
if($x<=6){
	$ans=1;
}elsif($x<=11){
	$ans=2;
}else{
	$val=int($x/11)*2;
    if($x%11==0){
    	$ans=$val;
    }elsif($x%11<=6){
    	$ans=$val+1;
    }else{
    	$ans=$val+2;
    }
}
print $ans;

Measured memory_bytes: 384
n,m=map(int,input().split())

lis=[1,n]
for i in range(m):
    l,r=map(int,input().split())
    if l>lis[0]:
        lis[0]=l
    if r<lis[1]:
        lis[1]=r

if lis[1]-lis[0]<0:
    print(0)
else:
    print(lis[1]-lis[0]+1)


Measured memory_bytes: 3060
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))

typedef long long ll;

int main(){
    string s; cin >> s;
    for(int i=0;i<3;i++){
        if(s[i]=='7'){cout << "Yes" << endl; return 0;}
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3628
package main

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

func main() {
	log.SetFlags(log.Lshortfile)
	N := nextInt()
	for i := 0; i <= 25; i++ {
		if (N-i*4)%7 == 0 && N >= i*4 {
			log.Println(i, i*4)
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}
func Max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func Min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func Sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func Abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	return p[i].b < p[j].b
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}
func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}


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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)

int main()
{
	LL H1, M1, H2, M2, K;
	cin >> H1 >> M1 >> H2 >> M2 >> K;

	LL start = H1 * 60 + M1;
	LL end = H2 * 60 + M2;
	LL ans = end - K - start;
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>

void selectionSort(int a[],int n){
  int i,j,minj,temp,count=0;
  for(i=0; i<n; i++ ){
    minj=i ;
    for(j=i;j<n;j++){
      if(a[j]<a[minj]){
        minj =j;
      }
    }
  if(i != minj){    
        temp=a[i];
        a[i]=a[minj];
        a[minj]=temp;
        count++;

}


  }

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

int main(void){
  int n,i,count ;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  selectionSort(a,n);

return 0;
}



Measured memory_bytes: 2136
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll n,q;cin>>n>>q;
    string s;cin>>s;
    vector<char>t(q),d(q);
    rep(i,q)cin>>t[i]>>d[i];
    ll ans=n;
    ll now=0;
    rep(i,q){
        if(t[i]==s[now]){
            if(d[i]=='R')now++;
            else now--;
        }
        if(now<0)break;
        if(now>=n)break;
    }
    if(now<0){
        ll l=0,r=n;
        while(r-l>1){
            ll k=(r+l)/2;
            ll im=k;
            rep(i,q){
                if(t[i]==s[im]){
                    if(d[i]=='R')im++;
                    else im--;
                }
                if(im<0)break;
                if(im>=n)break;
            }
            if(im<0)l=k;
            else r=k;
        }
        ans-=l+1;
    }
    now=n-1;
    rep(i,q){
        if(t[i]==s[now]){
            if(d[i]=='R')now++;
            else now--;
        }
        if(now<0)break;
        if(now>=n)break;
    }
    if(now>=n){
        ll l=-1,r=n-1;
        while(r-l>1){
            ll k=(r+l)/2;
            ll im=k;
            rep(i,q){
                if(t[i]==s[im]){
                    if(d[i]=='R')im++;
                    else im--;
                }
                if(im<0)break;
                if(im>=n)break;
            }
            if(im>=n)r=k;
            else l=k;
        }
        ans-=n-r;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 900
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
  ArrayList<String> s = nextCharArray();
  int max = 0;
  int count = 0;
  for(int i = 0; i < s.size(); i++){
  	if(s.get(i).equals("R")){
  		count++;
  	}else{
  		max = Math.max(max, count);
  		count = 0;
  	}
  }
  max = Math.max(max, count);
  myout(max);
	}
	//Method addition frame start



	//Method addition frame end
}


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

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n)   FOR(i,0,n)
#define RREP(i,n)   RFOR(i,0,n)
#define SORT(s) sort(s.begin(), s.end())
#define P pair<int, int>
#define mp make_pair

const double INF = 1e+09;
const int MOD = 1e9+7;

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

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 gcd(int a, int b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));}

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

vector<int> uniq(vector<int> vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return vec;}

vector<ll> divisor(ll n) {
vector<ll> ret;
for(int64_t i = 1; i * i <= n; i++) {
  if(n % i == 0) {
    ret.push_back(i);
    if(i * i != n) ret.push_back(n / i);
  }
}
  sort(begin(ret), end(ret));
  return (ret);
}
void permu(int n){
  vector<int> perm(n);
  REP(i, n) perm[i] = i;
do{
  cout << perm  << endl;
}
while (next_permutation(perm.begin(), perm.end()));
return;}

vector<pair<ll, int>> prime_div(ll n){
  vector<pair<ll, int>> res;
  for (ll i=2; i*i <= n;i++){
    if (n%i == 0){
      int a = 0;
      while(n%i == 0){
        n /= i;
        a++;
      }
      pair<ll, int> tmp;
      tmp.first = i;
      tmp.second = a;
      res.push_back(tmp);
    }
  }
  if (n != 1){
    pair<ll, int> now;
    now.first = n;
    now.second = 1;
    res.push_back(now);}
  return res;
}
  int n, m, q;
  vector<int> a, b, c, d;
  int ans = 0;
  vector<int> p(10, 1);

void dfs(int now){
  if (now == n+1){
    int tmp = 0;
    REP(i, q){
    if ((p[b[i]] - p[a[i]]) == c[i]) tmp += d[i];}
  ans =  max(tmp, ans);
  return;
  }
  for (int i=p[now]; i<=m; i++){
    p[now+1] = i;
    dfs(now+1);
}}


// printf("%.10f\n" , ans);
int main(void){
  ios::sync_with_stdio(false);
  cin >> n >> m >> q;
  a = b = c = d = vector<int> (q);
  REP(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
  dfs(0);
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//int n;
//vector< int > a(n);
//void solve() {
	//cin >> n;
	//a.resize(n);
	//for(auto& e:a) cin >> e;
//}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;
	//cin >> t;
	//while (t--) solve();
	int a,b;
	cin >> a >> b;
	cout << max({a+b,a-b,a*b});
	return 0;
}


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

int main(){
    int n;
    std::cin >> n;
    std::string S;
    std::cin >> S;
    int x = 0;
    int maxVal = 0;
    for(int i = 0; i < n; i++){
        if(S[i] == 'I') x++;
        else if(S[i] == 'D') x--;
        maxVal = std::max(x, maxVal);
    }

    std::cout << maxVal << std::endl;
    return 0;
}


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

int main(void)
{
  int a, b;
  cin >> a >> b;
  long long ans = a;
  while(1)
  {
    if(ans % b == 0)
    {
      break;
    }
    ans += a;
  }
  cout << ans << endl;
}


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

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int N;
  cin >> N;

  cout << N * N * N << endl;
  
  return 0;
}


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

@SuppressWarnings({"rawtypes", "unchecked"})
class Main {
    final static int INF = 1 << 28;
    final static long LNF = 1L << 60;
    final static double EPS = 1e-9;
    final static double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;

    static final long MOD = 1_000_000_007;

    public static void main(String[] args) throws Exception {
        final MyScanner sc = new MyScanner();
        long A;
        A = sc.nextLong();
        long B;
        B = sc.nextLong();
        solve(A, B);
    }

    static void solve(long A, long B){
        System.out.println(A*B/gcd(A,B));
    }

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

    static class MyScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        MyScanner(FileReader fileReader) {
            br = new BufferedReader(fileReader);
        }
 
        MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String nn() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String next() {
            String ans = "";
            try {
                ans = br.readLine();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
            return ans;
        }
 
        char nextChar() {
            return nn().charAt(0);
        }
 
        int nextInt() {
            return Integer.parseInt(nn());
        }
 
        long nextLong() {
            return Long.parseLong(nn());
        }
 
        double nextDouble() {
            return Double.parseDouble(nn());
        }
 
        Integer[] niArr0(int n) {
            Integer[] ar = new Integer[n];
            for (int i = 0; i < n; i++) {
                ar[i] = nextInt();
            }
            return ar;
        }
 
        Integer[] niArr1(int n) {
            Integer[] ar = new Integer[n + 1];
            for (int i = 1; i <= n; i++) {
                ar[i] = nextInt();
            }
            return ar;
        }
 
        Long[] nlArr0(int n) {
            Long[] ar = new Long[n];
            for (int i = 0; i < n; i++) {
                ar[i] = nextLong();
            }
            return ar;
        }
 
        Long[] nlArr1(int n) {
            Long[] ar = new Long[n + 1];
            for (int i = 1; i <= n; i++) {
                ar[i] = nextLong();
            }
            return ar;
        }
    }

}


Measured memory_bytes: 21332
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int n1 = n / 10000000;
        int n2 = (n % 10000000) / 1000000;
        int n3 = (n % 1000000) / 100000;
        int n4 = (n % 100000) / 10000;
        int n5 = (n % 10000) / 1000;
        int n6 = (n % 1000) / 100;
        int n7 = (n % 100) / 10;
        int n8 = n % 10;
        int harsh = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8;
        if (n % harsh == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n;
	cin>>n;
	cout<<power(n,3,2e18);
	
	return 0;
}

Measured memory_bytes: 256
INF=Float::INFINITY
n = gets.chomp.to_i
a = gets.chomp.split().map(&:to_i)

ans = INF
(-100).upto(100).each do |i|
  tmp = 0
  a.each do |e|
    tmp += (e-i) ** 2
  end
  ans = tmp if ans > tmp
end

puts ans





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


int main() {
	
	string s;
	cin >> s;
	vector<int> a(4);
	a.at(0) = s.at(0)-48, a.at(1) = s.at(1)-48;
	a.at(2) = s.at(2)-48, a.at(3) = s.at(3)-48;
	for(int i=0; i<8; i++){
		int sum = a.at(0);
		for(int j=0; j<3; j++){
			if(i & (1<<j)) sum += a.at(j+1);
			else sum -= a.at(j+1);
		}
		if (sum == 7){
			cout << a.at(0);
			for(int j=0; j<3; j++){
				if(i & (1<<j)) cout << '+';
				else cout << '-';
				cout << a.at(j+1);
			}
			cout << "=7" << endl;
			break;
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 256
arr = input().split()
K = int(arr[0])
A = int(arr[1])
B = int(arr[2])

n = 1 + K
x = 1
if K > A:
	x = B
	K -= A+1

	temp = int(K / 2)

	x += temp * (B-A)
	K -= temp * 2

	while K > 0:
		K -= 1
		x += 1

print(max(x, n))


Measured memory_bytes: 38256
def soinnsuubunnkai(p):
  dic = {}
  for i in range(2, int(p ** (1 / 2)) + 1):
    if p % i == 0:
      dic[i] = 0
    while p % i == 0:
      dic[i] += 1
      p //= i
  if p != 1:
    dic[p] = 1
  return dic
n, p = map(int, input().split())
dic = soinnsuubunnkai(p)
ans = 1
for k, v in dic.items():
  ans *= k ** (v // n)
print(ans)

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

int main()
{
    int n;
    cin >> n;
    int a[200005];
    int b[1000005]{0};
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[a[i]]++;
    }
    int ans = n;
    for(int i = 0; i < n; i++){
        b[a[i]]--;
        for(int j = 1; j * j <= a[i]; j++){
            if(a[i] % j) continue;
            if(b[j] + b[a[i] / j]){
                ans--;
                break;
            }
        }
        b[a[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 8272
# coding-utf8 #

a = int(input())
b = int(input())
c = int(input())
x = int(input())

# 全探索
# 全部0枚から初めてそれぞれの硬貨枚数までインクリメントしていって、
# ちょうどx円になるものを探す

count = 0

for i_500 in range(a + 1):
  for i_100 in range(b + 1):
    for i_50 in range(c + 1):
      sum = 500 * i_500 + 100 * i_100  + 50 * i_50
      if sum == x:
        count += 1

print(count)

Measured memory_bytes: 39664
from collections import deque

H,W = map(int,input().split())

S = []

for i in range(H):

    s = input()

    S.append(s)

lis = [ [True] * W for i in range(H) ]

ans = 0

for h in range(H):

    for w in range(W):

        if not lis[h][w]:
            continue
        
        q = deque([[h,w]])
        lis[h][w] = False

        if S[h][w] == "#":
            bnum = 1
            wnum = 0
        else:
            bnum = 0
            wnum = 1

        while len(q) > 0:

            now = q.popleft()
            nh = now[0]
            nw = now[1]

            if S[nh][nw] == "#":

                if nh > 0 and S[nh-1][nw] == "." and lis[nh-1][nw]:

                    wnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "." and lis[nh+1][nw]:

                    wnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "." and lis[nh][nw-1]:

                    wnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "." and lis[nh][nw+1]:

                    wnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])

            if S[nh][nw] == ".":

                if nh > 0 and S[nh-1][nw] == "#" and lis[nh-1][nw]:

                    bnum += 1
                    lis[nh-1][nw] = False
                    q.append([nh-1,nw])

                if nh < H-1 and S[nh+1][nw] == "#" and lis[nh+1][nw]:

                    bnum += 1
                    lis[nh+1][nw] = False
                    q.append([nh+1,nw])

                if nw > 0 and S[nh][nw-1] == "#" and lis[nh][nw-1]:

                    bnum += 1
                    lis[nh][nw-1] = False
                    q.append([nh,nw-1])

                if nw < W-1 and S[nh][nw+1] == "#" and lis[nh][nw+1]:

                    bnum += 1
                    lis[nh][nw+1] = False
                    q.append([nh,nw+1])
                    
        ans += wnum * bnum


print (ans)

                



Measured memory_bytes: 77164
N = gets.to_i
S_initial = [0]
S = gets.chomp.split("")

S_0_i = S_initial + S

#初期値
right_E = S_0_i.count("E")
left_W = 0
min_changeDirection = N


(1..N).each do |s_i|
  
  if S_0_i[s_i] == "E"
    right_E -= 1
  end
  
  if S_0_i[s_i - 1] == "W"
    left_W += 1
  end
  
  count_changeDirection = left_W + right_E
  #p "#{s_i}番目ではleft_W=#{left_W},right_E=#{right_E}"
  
  if min_changeDirection > count_changeDirection then
  min_changeDirection = count_changeDirection
  end
end
  
p min_changeDirection

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<string> S;

enum Alph { XA = 0, BA, BX };
ll cnt[3] = {};

signed main()
{
    ll ans = 0;

    cin >> N;
    S.resize(N);
    REP(i, N) {
        cin >> S[i];
        size_t tail = S[i].length() - 1;
        for(int j = 0; j < S[i].length() - 1; ++j) {
            if(S[i][j] == 'A' && S[i][j+1] == 'B') {
                ans++;
            }
        }
        if(S[i][0] == 'B') {
            if(S[i][tail] == 'A') { cnt[BA]++; }
            else { cnt[BX]++; }
        }
        else if(S[i][tail] == 'A') {
            cnt[XA]++;
        }
    }

    if(cnt[XA] >= 1 && cnt[BX] >= 1 && cnt[BA] >= 1) {
        // XA -> AB -> BX を優先的に組み合わせる
        cnt[XA]--;
        cnt[BX]--;
        ans += cnt[BA] + 1;
        ans += min(cnt[XA], cnt[BX]);
    }
    else if(cnt[XA] >= 1 && cnt[BX] >= 1 && cnt[BA] == 0) {
        ans += min(cnt[XA], cnt[BX]);
    }
    else if(cnt[XA] >= 1 && cnt[BA] >= 1 && cnt[BX] == 0) {
        cnt[XA]--;
        cnt[BA]--;
        ans += cnt[BA] + 1;
    }
    else if(cnt[BA] >= 1 && cnt[BX] >= 1 && cnt[XA] == 0) {
        cnt[BA]--;
        cnt[BX]--;
        ans += cnt[BA] + 1;
    }
    else if(cnt[BA] >= 1 && cnt[BX] >= 0 && cnt[XA] == 0) {
        ans += cnt[BA] - 1;
    }


    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

using lint = long long;
using plint = pair<double, lint>;

int N;
lint L;

deque<plint> deq;
double Qsum = 0;
lint Vnow = 0;

void trim()
{
    while (Vnow > L)
    {
        lint nuku = min(Vnow - L, deq.front().second);
        deq.front().second -= nuku;
        Vnow -= nuku;
        Qsum -= nuku * deq.front().first;
        if (deq.front().second == 0) deq.pop_front();
    }
}

void add(double tadd, lint vadd)
{
    if (deq.back().first < tadd) // 追加するほうが高温の場合、先頭から余剰分を抜いていく
    {
        deq.push_back(plint(tadd, vadd));
        Qsum += tadd * vadd;
        Vnow += vadd;
        trim();
    }
    else // 低温の場合、うしろとくっつけていく
    {
        if (deq.back().second + vadd >= L)
        {
            Qsum = deq.back().first * (L - vadd) + tadd * vadd;
            Vnow = L;
            deq.clear();
            deq.push_back(plint(Qsum / L, L));
        }
        else
        {
            double Qaddnew = deq.back().first * deq.back().second + tadd * vadd;
            lint vaddnew = deq.back().second + vadd;
            Qsum -= deq.back().first * deq.back().second;
            Vnow -= deq.back().second;
            deq.pop_back();
            add(Qaddnew / vaddnew, vaddnew);
        }
    }
}

void print()
{
    cout << setprecision(12) << Qsum / L << endl;
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> L;
    REP(_, N)
    {
        double t;
        lint v;
        cin >> t >> v;
        if (_ == 0)
        {
            deq.push_back(plint(t, v));
            Qsum = t * v;
            Vnow = v;
            print();
        }
        else
        {
            add(t, v);
            print();
        }
    }
}


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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,N) for(int i=0; i<N; i++)
#define cinv(v,N) vector<int> v(N); for(int i=0; i<N; i++){ cin >> v[i]; }
#define mt make_tuple
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define all(v) (v).begin(),(v).end()
const ll MOD2 = 998244353;
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; }

//繰り返し2乗法
ll power(ll x, ll y){//繰り返し2乗法
  if(y < 0){
    return 0;
  }else if(y == 0){
    return 1LL;
  }else if(y%2 == 0){//偶数
    return power(x,y/2)*power(x,y/2);
  }else{//奇数
    return power(x,y-1)*x;
  }
}

int main()
{
  //input
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll H, W, K; cin >> H >> W >> K; 
  vector<string> str(H); FOR(i,H){ cin >> str[i]; }
  
  //二次元累積和
  vvll sum(H+1,vll(W+1,0));
  FOR(i,H){ FOR(j,W){ sum[i+1][j+1] = str[i][j]-'0'; } }
  FOR(i,H+1){ FOR(j,W){ sum[i][j+1] += sum[i][j]; } }
  FOR(j,W+1){ FOR(i,H){ sum[i+1][j] += sum[i][j]; } }
  //FOR(i,H+1){ FOR(j,W+1){ cout << sum[i][j]; } cout << endl;}         
  
  //main
  ll ans = 1e18;
  for(int bit=0; bit<power(2,H-1); bit++){ //H-1桁目は絶対に1にならない。
    set<ll> st; st.insert(0); st.insert(H);
    for(int i=0; i<H; i++){
      if((bit>>i)%2){ st.insert(i+1); }//どこが切れているかを記憶。
    }
    
    ll tmp = 0;
    ll last = 0;
    
    set<ll> debug;
    
    for(int j=1; j<=W; j++){
      for(auto itr=st.begin(); itr != prev(st.end()); itr++){//*(prev(st.end()))はH。
        if((sum[*(next(itr))][j]-sum[*itr][j]-sum[*(next(itr))][last]+sum[*itr][last])>K){
          if(j-1 == last){
            goto ENDLOOP;
          }else{
            tmp ++; last = j-1;
            debug.insert(last);
            break;
          }
        }
      }
      if(j==W){
        for(auto itr=st.begin(); itr != prev(st.end()); itr++){
          if((sum[*(next(itr))][j]-sum[*itr][j]-sum[*(next(itr))][last]+sum[*itr][last])>K){
            goto ENDLOOP;
          }
        }
      }
    }
    tmp += st.size()-2;
    ans = min(ans, tmp);
    /*if(tmp == 6){
      for(auto s : st){ cout << s << " " ; } cout << " " << ans << endl;
      for(auto s : debug){ cout << s << " " ; } cout << " " << ans << endl;
    }*/
    ENDLOOP:{}
  }
  
  // output
  cout << ans << endl;
  
  //FOR(i,H+1){ FOR(j,W+1){ cout << sum[i][j]; } cout << endl;}

  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    ll x, mem = 1;
    while (1) {
        cin >> x;
        if (x == 0) return 0;
        cout << "Case " << mem << ": " << x << endl;
        mem++;
    }
    return 0;
}


Measured memory_bytes: 3132
class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        """
        N:要素数
        func:計算式(maxなど)
        intv:単位元
        """
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小(大)値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

#####

import bisect
import sys
input = sys.stdin.readline




N,D,A=map(int,input().split())
XH=[[0,0] for _ in range(N)]

for i in range(N):
    XH[i][0],XH[i][1]=map(int,input().split())
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]


sst=StarrySkyTree(N+1, max, 0)

for i in range(N):
    sst.update(i,i+1,XH[i][1])
    
cnt=0
for i in range(N):
    h=sst.query(i,i+1)
    if h>0:
        r=bisect.bisect_right(X,X[i]+2*D)
        bomb=(h+A-1)//A#切り上げ
        sst.update(i,r,-1*bomb*A)
        cnt+=bomb
        
print(cnt)

    
    

Measured memory_bytes: 87028
import itertools

def main():
    N = int(input())
    xy = [0] * N
    for i in range(N):
        A = int(input())
        xy_list = []
        for _ in range(A):
            x, y = map(int, input().split())
            xy_list.append((x, y))
        xy[i] = xy_list

    res = 0
    tf_gen = itertools.product([0, 1], repeat=N)
    for tf in tf_gen:
        honest = sum(tf)
        able = True
        for i, xy_l in enumerate(xy):
            for (x, y) in xy_l:
                if tf[x-1] != y and tf[i] == 1:
                    able = False
        if res < honest and able:
            res = honest
    print(res)


if __name__ == "__main__":
    main()

Measured memory_bytes: 74248