akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

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

        String S = sc.next();
        int count = 0;
        for (int i=0; i<3; i++) {
            if (S.charAt(i) == 'o') {
                count++;
            }
        }
        System.out.println(count*100 + 700);
    }
}



Measured memory_bytes: 21844
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#include<iostream>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define VI vector<int>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=205;
int n;LL a[MAXN];
LL p[MAXN];
bool check(LL x)
{
	for(int i=62;i>=0;i--)if(x&(1LL<<i))
	{
		if(!p[i])return false;
		x^=p[i];
	}return true;
}
void insert(LL x)
{
	for(int i=62;i>=0;i--)if(x&(1LL<<i))
	{
		if(!p[i]){p[i]=x;return ;}
		x^=p[i];
	}
}
char ch[MAXN];
void solve()
{
	memset(p,0,sizeof(p));
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	scanf("%s",ch+1);
	bool flag=true;
	for(int i=n;i>=1;i--)
	{
		if(ch[i]=='1')
			flag&=check(a[i]);
		else insert(a[i]);
	}
	if(!flag)pr2(1);
	else pr2(0);
}
int main()
{
	#ifdef Rose
		double BeginJudgeTime=clock();
	#endif
	for(int __=read();__;--__)solve();
	#ifdef Rose
		double EndJudgeTime=clock();
		cerr<<"JudgeTime is"<<" ";
		cerr<<(EndJudgeTime-BeginJudgeTime)/CLOCKS_PER_SEC<<endl;
	#endif
	return 0;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<ld> vld;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()

int main()
{
	fastIO;
	string s; cin >> s;
	int sum = 0;
	for(int i = 0; i < s.length(); i++) sum += s[i] - '0';
	if(sum % 9 == 0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define pb push_back
#define ll int 
#define mp make_pair
#define int long long 
#define ff first 
#define ss second
const int p=1e9 + 7;
const int mod=1e9 + 7;
const int Mod=1e9 + 7;
const int INF=1e9 + 7;
const int Maxn=1000000;
using namespace std;
 
void solve()
{
  int x,k,d;
  cin >> x >> k >> d;
  if(x<0)
  x=(-1)*x;
  int dd=x/d;
  if(k<dd)
  {
      x-=k*d;
      cout << x << endl;
  }
  else
  {
  x-=(dd*d);
  k-=dd;
  //cout << dd << " " << k << endl;
  if(k%2)
  {
     // cout << k << endl;
      x-=d;
      if(x<0)
      x=(-1)*x;
      cout << x << endl;
  }
  else
  {
      cout << x << endl;
  }
  
  }
  
 
}
 
signed main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
   int t;
   t=1;
   while(t--)
    solve();
  
 
}

Measured memory_bytes: 3640
// In the name of GOD
#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";

#define     IOS         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define 	setprecn(x) cout<<fixed<<setprecision(x);
#define 	ll          long long int
#define 	pb          push_back
#define 	pll         pair<ll,ll>
#define 	vll         vector<ll>
#define 	ff          first
#define 	ss          second
#define 	all(a)      (a).begin(),(a).end()
#define 	sz(x)       (ll)x.size()
#define 	mod         1000000007
#define 	inf         10000000000000007
#define 	rep(i,n)    for(ll i=0;i<n;i++)
#define 	repe(i,a,b) for(ll i=a;i<b;i++)
#define 	lbnd        lower_bound
#define 	ubnd        upper_bound
#define 	bs          binary_search

ll power(ll a,ll b,ll m=mod)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	ll c=power(a,b/2,m);
	if(b%2==0)
		return((c%m)*(c%m))%m;
	return ((((c%m)*(c%m))%m)*(a%m))%m;
}

/********************************************************/
//	d.erase(unique(all(d)), d.end());

double dis(double x1,double y1,double x2,double y2)
{
	return sqrt(((x2-x1)*(x2-x1))+((y2-y1)*(y2-y1)));
}
int main()
{
	IOS;
	ll n,k,m,i,j,c=0,cs=0,t;
	t=1;

	// cin>>t;
	string s;
	while(t--)
	{
		cin>>n;
		// n=s.length();
		double x[n],y[n];
		rep(i,n)
		{
			cin>>x[i]>>y[i];
		}
		double p=0;
		rep(i,n)
		{
			for(j=i+1;j<n;j++)
			{
				p+=dis(x[i],y[i],x[j],y[j]);
			}
		}
		p=p*2.0;
		p=p/(n*1.0);
		// p=p/(n-1);
		setprecn(10);
		cout<<p;

		if(t!=0)
	   		cout<<"\n";
	}
	return 0;
}

Measured memory_bytes: 256
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = [int(p) for p in input().split()]
    Ex = [0] * N
    for i, p in enumerate(P):
        total = (p + 1) * p / 2
        Ex[i] = total / p
    maxEx = sum(Ex[:K])
    now = maxEx
    for i in range(N - K):
        now -= Ex[i]
        now += Ex[i + K]
        maxEx = max(maxEx, now)
    print(maxEx)

    return 0

if __name__ == "__main__":
    solve()

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

const int INF = 1e+9;

int ans[16][512];
int n, s;

int dfs(int a, int sum, int c){
	ans[a][sum]++;
	if(a >= 10)
		return 0;
	
	int res = 0;
	for(int i = 0; i < 10; ++i){
		if(!(c >> i & 1)){
			res += dfs(a + 1, sum + (a + 1) * i, c | 1 << i);
		}
	}
	return res;
}

int main() {
	dfs(0, 0, 0);
	while(cin >> n >> s){
		cout << (s > 510 ? 0 : ans[n][s]) << endl;
	}
	return 0;
}

Measured memory_bytes: 1180
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int ans = n;
        for (int i = 0; i < n; i++) {
            if (sc.nextInt() < k) {
                ans -= 1;
            }
        }
        System.out.println(ans);
}}

Measured memory_bytes: 47276
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;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 REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007

ll h, w, d, r[444514], s[400][400];
vector<pair<ll, ll>> p(114514);
int main() {
	cin >> h >> w >> d;
	REP(i, h) REP(j, w)cin >> s[i][j];
	REP(i, h) {
		REP(j, w) {
			p[s[i][j]] = make_pair(i, j);
		}
	}
	REPO(i, h * w) {
		if (i + d <= h * w) {
			r[i + d] = r[i] + abs(p[i].first - p[i + d].first) + abs(p[i].second - p[i + d].second);
		}
	}
	ll q;
	cin >> q;
	REP(i, q) {
		ll a, b;
		cin >> a >> b;
		cout << r[b] - r[a] << endl;
	}
}



Measured memory_bytes: 4608
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const unsigned int mod = 1000000007;
//const unsigned int mod = 998244353;

struct mint {
	unsigned int x;
	mint():x(0) {}
	mint(int64_t x_) {
		int64_t v = int64_t(x_ % mod);
		if(v < 0) v += mod;
		x = (unsigned int)v;
	}
	static mint row(int v) {
		mint v_;
		v_.x = v;
		return v_;
	}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		uint64_t z = x;
		z *= a.x;
		x = (unsigned int)(z % mod);
		return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
	friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
	mint &operator++() {
		x++;
		if(x == mod) x = 0;
		return *this;
	}
	mint &operator--() {
		if(x == 0) x = mod;
		x--;
		return *this;
	}
	mint operator++(int) {
		mint result = *this;
		++*this;
		return result;
	}
	mint operator--(int) {
		mint result = *this;
		--*this;
		return result;
	}
	mint pow(int64_t t) const {
		mint x_ = *this, r = 1;
		while(t) {
			if(t&1) r *= x_;
			x_ *= x_;
			t >>= 1;
		}
		return r;
	}
	//for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

#define N 410

//head

int n, c, a[N], b[N];
mint dp[N], dpp[N];
mint *now = dp, *pre = dpp;

int main() {
	scanf("%d%d", &n, &c);
	rep(i, n) scanf("%d", a+i);
	rep(i, n) scanf("%d", b+i);
	pre[0] = 1;
	rep(i, n) {
		memset(now, 0, sizeof(dp));
		for(int j = a[i]; j <= b[i]; j++) {
			mint x = pre[0];
			rep(k, c+1) {
				now[k] += x;
				x = x*j + pre[k+1];
			}
		}
		swap(now, pre);
	}
	printf("%d\n", pre[c].x);
}

Measured memory_bytes: 3800
package main

import "fmt"

func main() {
	var s string
	var k int

	fmt.Scanf("%s", &s)
	fmt.Scanf("%d", &k)

	var c int = 0
	var head int = 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			head++
		} else {
			break
		}
	}
	if head == len(s) {
		if head*k%2 == 0 {
			c = head * k / 2
		} else {
			c = (head*k - 1) / 2
		}
		fmt.Printf("%d\n", c)
		return
	}

	var back int = 1
	for i := len(s) - 1; i > 0; i-- {
		if s[i] == s[i-1] {
			back++
		} else {
			break
		}
	}

	for i := 0; i < len(s)-1; i++ {
		if s[i] == s[i+1] {
			c++
			i++
		}
	}

	c *= k

	if s[0] == s[len(s)-1] {
		var m = head + back

		if m%2 == 0 {
			c += (m / 2) * (k - 1)
		} else {
			c += ((m - 1) / 2) * (k - 1)
		}
		if head != 1 {
			if head%2 == 0 {
				c -= (head / 2) * (k - 1)
			} else {
				c -= ((head - 1) / 2) * (k - 1)
			}
		}
		if back != 1 {
			if back%2 == 0 {
				c -= (back / 2) * (k - 1)
			} else {
				c -= ((back - 1) / 2) * (k - 1)
			}
		}
	}

	fmt.Printf("%d\n", c)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination MOD prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} comb(10000007);
// comb(5, 2) → 10, comb.p(5, 2) → 20, comb.fact[4] → 24

int N;

mint power(int x) {
  // 2のx乗をmintで返す
  if (x == 0) return 1;
  mint res = power(x / 2);
  res *= res;
  if (x&1) res *= 2;
  return res;
}

mint choose(int x) {
  // nCxをmintで返す
  mint res = 1;
  rep(i, x) {
    res *= (N-i);
    res /= (x-i);
  }
  return res;
}
int main() {
  int A, B;
  cin >> N >> A >> B;
  mint ans = power(N);
  ans -= (choose(A) + choose(B) + 1);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 159304
#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (signed)(a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define MOD 1000000007
#define pb push_back
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
#define tp(a, b, c) make_tuple(a, b, c)
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
//------------------変数-----------------------//
//-------------------関数----------------------//
ll n, x, a[2001];
ll miniitr[2001][2001];
ll next(ll num) {
  if (num == n - 1) {
    return 0;
  }
  return num + 1;
}
ll prev(ll num) {
  if (num == 0) {
    return n - 1;
  }
  return num - 1;
}
int main() {
  cin >> n >> x;
  REP(i, n) { cin >> a[i]; }
  REP(i, n) {
    ll itr = i;
    ll p = a[i];
    REP(kaisuu, n) {
      miniitr[i][kaisuu] = min(a[itr], p);
      p = miniitr[i][kaisuu];
      itr = prev(itr);
    }
  }
  ll mini = INF;
  REP(i, n) {
    ll cnt = x * i;
    REP(j, n) { cnt += miniitr[j][i]; }
    mini = min(cnt, mini);
  }
  cout << mini << endl;
}


Measured memory_bytes: 31488
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yassin
 */

#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstdlib>
#include <tuple>
#include <queue>
#include <functional>
#include <stack>
#include <numeric>
#include <cassert>
#include <sstream>

using namespace std;

struct bills {
    int a = 0, b = 0, c = 0;
    int poss = 0;
};

class abc085_c {
public:
    void solve(istream& in, ostream& out) {
        int N, Y;
        in >> N >> Y;
        Y /= 1000;
        vector<bills> dp(Y + 1);
        dp[0].poss = 1;
        for (int i = 0; i < N; ++i) {
            for (int j = Y; j >= 0; --j) {
                dp[j].poss = 0;
                if (j - 1 >= 0 && dp[j - 1].poss) {
                    dp[j] = dp[j - 1];
                    ++dp[j].c;
                }
                if (j - 5 >= 0 && dp[j - 5].poss) {
                    dp[j] = dp[j - 5];
                    ++dp[j].b;
                }
                if (j - 10 >= 0 && dp[j - 10].poss) {
                    dp[j] = dp[j - 10];
                    ++dp[j].a;
                }
            }
        }
        if (dp[Y].poss) {
            out << dp[Y].a << " " << dp[Y].b << " " << dp[Y].c << "\n";
        } else {
            out << "-1 -1 -1\n";
        }
    }
};


int main() {
	std::ios::sync_with_stdio(false); cin.tie(nullptr);
	abc085_c solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

bool comp(const int& e1, const int& e2) {
  return e1 > e2;
}

int main() {
    int n, i, ans=0;
    vector<int> p;
    cin >> n;
    for(i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        p.push_back(tmp);
        ans += tmp;
    }
    sort(p.begin(), p.end(), comp);
    cout << ans - (p[0]/2) << endl;
    return 0;
}

Measured memory_bytes: 256
H, W, M = map(int, input().split())
cntH = {}
cntW = {}
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb.add((h-1, w-1))
    cntH[h-1] = cntH.get(h-1, 0) + 1
    cntW[w-1] = cntW.get(w-1, 0) + 1

maxH, maxW = max(cntH.values()), max(cntW.values())
max_H_list = [kv[0] for kv in cntH.items() if kv[1] == maxH]
max_W_list = [kv[0] for kv in cntW.items() if kv[1] == maxW]

ans = maxH + maxW - 1
flag = False
for i in max_H_list:
    for j in max_W_list:
        if (i, j) not in bomb:
            flag = True
            break
    else:
        continue
    break
if flag:
    ans += 1

print(ans)

Measured memory_bytes: 99240
c = []
for i in range(3):
    c.append(list(map(int, input().split())))
a = [0, 0, 0]
b = [0, 0, 0]
a[0] = 0
b[0] = c[0][0]
b[1] = c[0][1]
b[2] = c[0][2]
a[1] = c[1][0]-b[0]
a[2] = c[2][0]-b[0]

tot = 0
for i in range(3):
    for j in range (3):
        if a[i]+b[j] != c[i][j]:
            tot += 1
            break
print(["No", "Yes"][tot == 0])


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int N,W;
vector<int> A;

ll dp[202][10010];
ll sum[202];

void add(ll &a,ll b){
    a=(a+b)%MOD;
}

int main(){
  cin>>N>>W;
  A.resize(N);
  rep(i,N) cin>>A[i];

  sort(A.begin(),A.end());
  for(int i=0;i<N;i++) sum[i+1]=sum[i]+A[i];
  reverse(A.begin(),A.end());

  dp[0][0]=1;
  for(int i=0;i<N;i++){
      for(int j=0;j<=W;j++){
          if(j+A[i]<=W) add(dp[i+1][j+A[i]],dp[i][j]);
          add(dp[i+1][j],dp[i][j]);
      }
  }

  ll ans=0;
  if(sum[N]<=W) ans++;//all

  for(int i=0;i<N;i++){
      ll s=sum[N-i-1];
      for(int j=0;j<=W-s;j++){
          if(s+j+A[i]>W) add(ans,dp[i][j]);
      }
  }

  cout<<ans<<endl;

  return 0;
}



Measured memory_bytes: 18644
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define dd double
#define ld long double
#define sl(n) scanf("%lld", &n)
#define si(n) scanf("%d", &n)
#define sd(n) scanf("%lf", &n)
#define pll pair <ll, ll>
#define pii pair <int, int>
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define inf (1LL << 62)
#define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
#define for1(i, stop) for(ll i = 1; i <= stop; ++i)
#define for0(i, stop) for(ll i = 0; i < stop; ++i)
#define rep1(i, start) for(ll i = start; i >= 1; --i)
#define rep0(i, start) for(ll i = (start-1); i >= 0; --i)
#define ms(n, i) memset(n, i, sizeof(n))
#define casep(n) printf("Case %lld:", ++n)
#define pn printf("\n")
#define pf printf
#define EL '\n'
#define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
    ll l, r, d;
    cin >> l >> r >> d;

    ll ans = r / d;
    ans -= (l-1)/d;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3628
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int err() {
	printf("-1\n");
	return 0;
}

int main() {
	string s;
	cin >> s;
	int n = s.length();
	if (s[n - 1] == '1')return err();
	if (s[0] == '0')return err();
	REP(i, n-1) if (s[i] != s[n - i - 2])return err();
	VI comp;
	comp.PB(0);
	for (int i = 0; i <= n - i - 2; i++)if(s[i] == '1')comp.PB(i + 1);
	int k = comp.size();
	vector<PII> ans;
	REP(i, k)ans.PB(MP(i, i + 1));
	int sz = 0;
	REP(i, comp.size()) {
		while (sz < comp[i]) {
			ans.PB(MP(i - 1, ++k));
			sz++;
		}
		sz++;
	}
	while (sz < n-1) {
		ans.PB(MP(comp.size() - 1, ++k));
		sz++;
	}
	for (auto e : ans)printf("%d %d\n", e.first + 1, e.second + 1);
	return 0;
}


Measured memory_bytes: 2612
A, B, M = [int(i) for i in input().split(' ')]
A_list = [int(i) for i in input().split(' ')]
B_list = [int(i) for i in input().split(' ')]

min_val = min(A_list) + min(B_list)
for k in range(M):
    x,y,c = [int(i) for i in input().split(' ')]
    tmp = A_list[x-1] + B_list[y-1] - c
    if tmp < min_val:
        min_val = tmp
if min_val < tmp:
    print(min_val)
else:
    print(tmp)


Measured memory_bytes: 18488
#include <vector>
#include <functional>

using namespace std;

template<typename T>
class SegmentTree
{
    int n;
    function<T(T,T)> op;
    vector<T> V;

    T q(int l, int r)
    {
        if (l >= r)
            return V[0];
        T a = q((l+1)/2, r/2);
        if (l%2 != 0)
            a = op(a, V[l]);
        if (r%2 != 0)
            a = op(a, V[r-1]);
        return a;
    }

public:
    SegmentTree(int n_, function<T(T,T)> op, T init):
        op(op)
    {
        n = 1;
        while (n < n_)
            n *= 2;
        V = vector<T>(2*n, init);
        for (int i=n-1; i>0; i--)
            V[i] = op(V[i*2], V[i*2+1]);
    }

    T get(int p) const
    {
        return V[p+n];
    }

    void set(int p, T v)
    {
        p += n;
        V[p] = v;
        for (p/=2; p>0; p/=2)
            V[p] = op(V[p*2], V[p*2+1]);
    }

    //  init OP v[l] OP v[l+1] OP ... OP v[r-1]
    T query(int l, int r)
    {
        return q(l+n, r+n);
    }
};

#include <iostream>
#include <algorithm>

int main()
{
    int N;
    cin>>N;
    vector<int> P(N);
    for (int &p: P)
        cin>>p, p--;

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

    SegmentTree<int> L(N, [](int x, int y){return max(x, y);}, -1);
    SegmentTree<int> R(N, [](int x, int y){return min(x, y);}, N);

    long long ans = 0;
    for (int i=N-1; i>=0; i--)
    {
        int p = T[i];
        int l1 = L.query(0, p);
        int l2 = L.query(0, l1);
        int r1 = R.query(p+1, N);
        int r2 = R.query(r1+1, N);
        L.set(p, p);
        R.set(p, p);

        if (0<=l1)
            ans += (long long)(i+1)*(l1-l2)*(r1-p);
        if (r1<N)
            ans += (long long)(i+1)*(p-l1)*(r2-r1);
    }
    cout<<ans<<endl;
}


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

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

  string S; cin >> S;
  int ans = 0;
  int N = S.size();
  for (int i = 0; i < N; i++) {
    if (S[i] != S[N - 1 - i]) ans++;
  }
  cout << ans / 2 << '\n';
  return 0;
}

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

int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    int n = a*x + b*y;
    int m = c*2*max(x,y);
    int l;
    if (x < y) l = c*2*x + b*(y-x);
    else       l = c*2*y + a*(x-y);

    cout << min({n, m, l}) << endl;
}

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

const int N=1e5+30;
typedef long long ll;
int n,k,arr[N];
int dp[N];
ll solve(int i){
    if(i>=n)return 1e15;
    if(i==n-1){
        return 0;
    }

    if(dp[i]!=-1)return dp[i];
    ll mn=1e18;
    for(int j=1;j<=k;j++){
        ll path1=abs(arr[i]-arr[i+j])+solve(i+j);
        mn=min(path1,mn);
    }
    return dp[i]= mn;
}
int main()
{
    memset(dp,-1,sizeof dp);
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",arr+i);
    cout<<solve(0)<<endl;
}



Measured memory_bytes: 5760
#include <iostream>
#define MAX 101

using namespace std;

bool flag[MAX][MAX];
int t[MAX][2];
int n;

void dfs(int num){
	static int cnt = 1;
	
	if(t[num][0] == 0)t[num][0] = cnt++;
	else return;
	for(int i=1;i<=n;++i){
		if(flag[num][i] == true){
			dfs(i);
		}
	}
	t[num][1] = cnt++;
}

int main(){
	int u, k, v, i, j; 
	
	cin >> n;
	for(i=1;i<=n;++i){
		cin >> u >> k;
		for(j=0;j<k;++j){
			cin >> v;
			flag[u][v] = true;
		}
		 
	}
	for(int i=1;i<=n;++i)dfs(i);
	for(int i=1;i<=n;++i)cout << i << " " << t[i][0] << " " << t[i][1] << endl;
	
	return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void){
    long long int a, b, k, n, i, j;
    scanf("%lld %lld", &n, &k);
    long long int flip[n+1];
    for(i=1; i<=n; i++){
        if(k>i){
        flip[i] = (long long int)log2((double)k/i) + 1;
        if((k%i==0) && !(k/i & (k/i-1))) flip[i]--;
        }else flip[i] = 0;
    }
    double ans=0, po;
    for(i=1; i<=n; i++){
        po = 1;
        for(j=0; j<flip[i]; j++) po = po*2;
        ans += 1/po;
    }
    printf("%.10f", ans/n);


}

Measured memory_bytes: 896
from math import factorial as fact
import math
import sys
import itertools
import numpy as np
from collections import Counter
import datetime


#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(range(n),r))



def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			




N=input1()

print(N**3)






Measured memory_bytes: 12452
n = int(input())
v = list(map(int,input().split()))

c = {0:{}, 1:{}}
for i,vi in enumerate(v):
    r = i % 2
    if vi not in c[r]:
        c[r][vi] = 0
    c[r][vi] += 1

c0 = sorted(c[0].items(), key=lambda x:-x[1])
c1 = sorted(c[1].items(), key=lambda x:-x[1])

if c0[0][0] == c1[0][0]:
    if len(c0) < 2:
        c0.append((-1,0))
    if len(c1) < 2:
        c1.append((-1,0))
    print(n - max(c0[0][1] + c1[1][1], c0[1][1] + c1[0][1]))
else:
    print(n - c0[0][1] - c1[0][1])


Measured memory_bytes: 20764
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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

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

__attribute__((constructor)) void initial() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int S, W;
  cin >> S >> W;
  
  cout << (W>=S?"unsafe":"safe") << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define MP make_pair
#define PB push_back
#define PII pair<int, int>
typedef long long LL;
const LL P = 998244353;
const int N = 2e5+10;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct point{
	int x,y,id;
	bool operator<(point b){
		return x<b.x || x==b.x && y<b.y;
	}
}a[N],b[N];
struct dat{
	int val,id;
}x[N];
int n;
int lu[N], ld[N], ru[N], rd[N], tr[N];
LL pw2[N];

LL pw(int x){
	return x<0 ? 0 :pw2[x];
}

void add(int x,int val){
	for(;x<=n;x+=x&-x)tr[x]+=val;
}
int get(int x){
	int res = 0;
	for(;x;x-=x&-x)res += tr[x];
	return res;
}

void calc(int cnt[]){
	memset(tr,0,sizeof tr);
	memcpy(b,a,sizeof b);
	rep(i,1,n) b[i].id = i;
	sort(b+1,b+n+1);
	rep(i,1,n){
		add(b[i].y,1);
		cnt[b[i].id] = get(b[i].y-1);
	}
}

int main(){
	scanf("%d",&n);
	pw2[0] = 1;
	rep(i,1,n) pw2[i] = pw2[i-1] * 2 % P;
	rep(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
	
	// discretize
	rep(i,1,n)x[i] = {a[i].x,i};
	sort(x+1,x+n+1,[](dat a,dat b){return a.val<b.val;});
	rep(i,1,n)a[x[i].id].x = i;
	rep(i,1,n)x[i] = {a[i].y,i};
	sort(x+1,x+n+1,[](dat a,dat b){return a.val<b.val;});
	rep(i,1,n)a[x[i].id].y = i;
	//rep(i,1,n)cout<<a[i].x<<" "<<a[i].y<<endl;
	
	calc(ld);
	rep(i,1,n)a[i].y=n+1-a[i].y;
	calc(lu);
	rep(i,1,n)a[i].x=n+1-a[i].x;
	calc(ru);
	rep(i,1,n)a[i].y=n+1-a[i].y;
	calc(rd);
	//rep(i,1,n)cout<<ld[i]<<" "<<lu[i]<<" "<<rd[i]<<" "<<ru[i]<<endl;
	
	LL ans = pw2[n-1] * n % P;
	rep(i,1,n){
		LL tmp = (pw(ld[i])-1) * (pw(ru[i])-1) % P * pw(lu[i]) % P * pw(rd[i]) % P;
		tmp += pw(ld[i]) * pw(ru[i]) % P * (pw(lu[i])-1) % P * (pw(rd[i])-1) % P;
		tmp -= (pw(ld[i])-1) * (pw(ru[i])-1) % P * (pw(lu[i])-1) % P * (pw(rd[i])-1) % P;
		ans = (ans + tmp + P*10) % P;
		//cout<<i<<" "<<tmp<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <stack>
#define FOR(arg, ini, end) for(int arg = ini; arg < end; arg++)


using namespace std;
int main(int argc, const char * argv[]) {
    
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<numeric>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//最大公約数
template<class T> T gcd(T a, T b)
{
	while (true)
	{
		T r;
		if (a%b == 0) return b;
		else
		{
			r = a % b;
			a = b;
			b = r;
		}
	}
}
//最小公倍数
template<class T> T lcm(T a, T b)
{
	return a / gcd(a, b)*b;
}
//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn = 1, Kr = 1, Knr = 1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}
//int型10進数をord桁のstring型2進数に変換する
string binary(int x,int ord)
{
	int y;
	string ans = "";
	for (int i = 0; i < ord; i++)
	{
		y = x / pow(2, ord - 1 - i);
		y %= 2;
		if (y == 0) ans += "0";
		else ans += "1";
	}

	return ans;
}


/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/

int N, M;
pair<int, int> path[30];

bool use[10];
int perm[10];
int ans;

int solve(int pos)
{
	if (pos == N)
	{
		/*for (int i = 0; i < N; i++)
		{
			cout << perm[i] << " ";
		}*/

		bool jud = false;
		for (int i = 0; i < N-1; i++)
		{
			int a = min(perm[i], perm[i + 1]) + 1;
			int b = max(perm[i], perm[i + 1]) + 1;

			for (int j = 0; j < M; j++)
			{
				if (path[j].first == a && path[j].second == b)
				{
					jud = true;
					break;
				}
				else jud = false;
			}

			if (!jud)
			{
				/*cout << "F" << endl;*/
				return 0;
			}
		}

		/*cout << "T" << endl;*/
		return 1;
	}
	
	int res = 0;
	for (int i = 0; i < N; i++)
	{
		if (!use[i])
		{
			use[i] = true;
			perm[pos] = i;
			res += solve(pos + 1);
			use[i] = false;
		}
	}

	return res;
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> path[i].first;
		cin >> path[i].second;
	}

	use[0] = true;

	cout << solve(1) << endl;

	return 0;
}


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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
vector<LL>v;
int main()
{
    LL n;
    LL s=0;
    cin>>n;
    LL x=1;
    for(LL i=0; i<63; i++)
    {
       if(x>n)
       {
           cout<<x-1;
           return 0;
       }
        x=x*2;
    }
    cout<<s;
}




Measured memory_bytes: 256
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
data_yoko = [[0]*(w+1) for _ in range(h)]
for i in range(w):
    for j in range(h):
        if s[j][i] == "1":
            data_yoko[j][i+1] = 1
        data_yoko[j][i+1] += data_yoko[j][i]
data_tate = [[0]*w for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "1":
            data_tate[i+1][j] = 1
        data_tate[i+1][j] += data_tate[i][j]

ans = h*w
for case in range(2**(h-1)):
    now = 0
    use = []
    for bit in range(h-1):
        if case>>bit & 1:
            use.append(bit+1)
            now += 1
    use.append(h)
    left = [0]*len(use)
    pre = -1
    check1 = True
    check2 = True
    #print(*use)
    for i in range(w):
        for j in range(len(use)):
            to = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
            if k < to:
                check1 = False
            if to + left[j] > k:
                check2 = False
            left[j] += to
        #print(left,check1,check2)
        if not check1:
            break
        if check2:
            continue
        for j in range(len(use)):
            left[j] = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
        now += 1
        check2 = True
    if check1:
        #print(now,use)
        ans = min(ans,now)

print(ans)


Measured memory_bytes: 45916
// Code by ajcxsu
// Problem: exhausted

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
struct Pos { int x, y; } p[N];
bool cmp(const Pos &a, const Pos &b) { return a.x<b.x; }

#define ls x<<1
#define rs x<<1|1
int mx[N<<2], sum[N<<2];
void updata(int x, int l, int r, int d, int w) {
    if(l==r) { mx[x]+=w, sum[x]+=w; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls, l, mid, d, w);
    else updata(rs, mid+1, r, d, w);
    mx[x]=max(mx[rs], mx[ls]+sum[rs]);
    sum[x]=sum[ls]+sum[rs];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, ans=0, ex=0;
    cin>>n>>m;
    if(m<n) ex=n-m, m=n;
    for(int i=1;i<=n;i++) {
        cin>>p[i].x>>p[i].y;
        if(p[i].x>p[i].y) p[i].x=p[i].y;
    } sort(p+1, p+1+n, cmp);
    for(int i=0;i<=m;i++) updata(1, 0, m+1, i, -1);
    for(int i=1;i<=n;i++) {
        updata(1, 0, m+1, p[i].y, 1);
        ans=max(ans, -p[i].x+mx[1]);
    }
    cout<<ans+ex<<endl;
    return 0;
}


Measured memory_bytes: 7936
#include<stdio.h>
#define MAX 10000
#define NIL -1

typedef struct{
  int parent;
  int left;
  int right;
}Node;

Node tree[MAX];
int depth[MAX],height[MAX];

void setDepth(int,int);
int setHeight(int);
int Sibling(int);
void Print(int);

int main(){
  int n,i,num,l,r;
  int root = 0;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    tree[i].parent = NIL;
  }
  for(i = 0; i < n ;i++){
    scanf("%d%d%d",&num,&l,&r);
    tree[num].left = l;
    tree[num].right = r;
    if(l != NIL) tree[l].parent = num;
    if(r != NIL) tree[r].parent = num;
  }
  for(i = 0; i < n; i++){
    if(tree[i].parent == NIL)root = i;
  }

  setDepth(root,0);
  setHeight(root);

  for(i = 0; i < n ;i++)Print(i);

  return 0;
}

int Sibling(int x){
  if(tree[x].parent == NIL) return NIL;
  if(tree[tree[x].parent].left != x && tree[tree[x].parent].left != NIL)return tree[tree[x].parent].left;
  if(tree[tree[x].parent].right != x && tree[tree[x].parent].right != NIL)return tree[tree[x].parent].right;

  return NIL;
}
void setDepth(int x,int y){
  if(x == NIL) return;
   depth[x] = y;
   setDepth(tree[x].left, y+1);
   setDepth(tree[x].right, y+1);
}

int setHeight(int x){
  int h1 = 0, h2 = 0;
  if(tree[x].left != NIL) h1 = setHeight(tree[x].left) + 1;
  if(tree[x].right != NIL) h2 = setHeight(tree[x].right) + 1;
  if(h1 > h2) return height[x] = h1;
  else return height[x] = h2;
}

void Print(int x){
  int degree = 0;
  printf("node %d: ",x);
  printf("parent = %d, ",tree[x].parent);
  printf("sibling = %d, ",Sibling(x));
  if(tree[x].left != NIL) degree++;
  if(tree[x].right != NIL) degree++;
  printf("degree = %d, ",degree);
  printf("depth = %d, ",depth[x]);
  printf("height = %d, ",height[x]);

  if(tree[x].parent == NIL){
  printf("root\n");
  }
  else if(tree[x].left == NIL && tree[x].right == NIL){
  printf("leaf\n");
  }
  else printf("internal node\n");
}



Measured memory_bytes: 2032
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */


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

class ACurtain {
public:
	void solve(std::istream& in, std::ostream& out) {
        int a,b;
        in >> a >> b;
        int ans=max(0,a-2*b);
        out << ans << endl;
	}
};


int main() {
	ACurtain solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}


//for(int i = ; i < ; i++){}

int main(){
  int n,m;
  cin>>n>>m;
  cout<<(n-1)*(m-1)<<endl;
  return 0;
}




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

using namespace std;
#define int long long


signed main(){
  int k;cin>>k;
  string s;cin>>s;
  if(s.size()>k){
    for(int i=0;i<k;i++) cout<<s[i];cout<<"...";
  }else{
    cout<<s;
  }
  return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
#define very_slow       ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vec             vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define inf             1e18
#define MAX             1e9
#define MIN            -1e9
#define no_of_test(x)        int x; cin>>x; while(x--)
//Actual Code Is At The Top
const int mod = 1e9 + 7;
int gcd(int a, int b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
int binary_exponentation(int a, int b)
{
	int ret = 1;
	while (b)
	{
		if (b & 1) ret = (ret * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ret;
}
int32_t main()
{   
	very_slow
//	no_of_test(x)
	{  
         int a[3][3];
		 for(int i=0;i<3;i++)
		 {
             for(int j=0;j<3;j++)
			 {
				 cin>>a[i][j];
			 }
		 }
		 int q;
		 cin>>q;
		 while(q--)
		 {
			 int n;
			 cin>>n;
			 for(int i=0;i<3;i++)
		    {
             for(int j=0;j<3;j++)
			 {
				 if(a[i][j]==n)
				 {
					 a[i][j]=1;
					 break;
				 }
		 	 }
	       }
		 }
		 string s="No";
		 for(int i=0;i<3;i++)
		 {
			 if(a[i][0]==1 && a[i][1]==1 && a[i][2]==1)
			 {
				 s="Yes";
				// break;
				 //continue;
			 }
		 }
		 for(int i=0;i<3;i++)
		 {
			 if(a[0][i]==1 && a[1][i]==1 && a[2][i]==1)
			 {
				s="Yes";
				// break;
				 //continue;
			 }
		 }
         if(a[0][0]==1&&a[1][1]==1&&a[2][2]==1) s="Yes";
		 if(a[2][0]==1&&a[1][1]==1&&a[0][2]==1) s="Yes";
		 cout<<s<<'\n';
		 
	}
	return 0;
}

Measured memory_bytes: 3584
from collections import deque


class Dinic:
    def __init__(self, v, inf=10**9 + 7):
        self.V = v
        self.inf = inf
        self.G = [list() for _ in range(v)]
        self.level = [-1 for _ in range(v)]
        self.iter = [0] * v

    def addedge(self, fr, to, cap):
        """
        G[fr] = [to, cap, rev]
        """
        go = [to, cap, None]
        go[2] = back = [fr, 0, go]
        self.G[fr].append(go)
        self.G[to].append(back)

    def bfs(self, st, en):
        q = deque([st])
        self.level = [-1 for _ in range(self.V)]
        self.level[st] = 0
        while q:
            cur = q.popleft()
            for x, cap, _ in self.G[cur]:
                if cap and self.level[x] < 0:
                    self.level[x] = self.level[cur] + 1
                    q.append(x)
        return self.level[en] > 0

    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.iter[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.iter = list(map(iter, self.G))
            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
        return flow
      
      
      
H, W = map(int, input().split())
dinic = Dinic(200)
for y in range(H):
  s = input()
  for x in range(W):
    if s[x] == 'o':
      dinic.addedge(y, x+100, 1)
      dinic.addedge(x+100, y, 1)
    elif s[x] == 'S':
      sy, sx = y, x
      dinic.addedge(y, x+100, 10**5)
      dinic.addedge(x+100, y, 10**5)
    elif s[x] == 'T':
      ty, tx = y, x
      dinic.addedge(y, x+100, 10**5)
      dinic.addedge(x+100, y, 10**5)
print(-1 if sy == ty or sx == tx else dinic.flow(sy, ty))

Measured memory_bytes: 7540