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

int main(){
  int N,M;
  cin >> N >> M;
  int K,tmp,A[M],res=0;
  for(int h=0;h<M;h++){
    A[h] = 0;
  }
  
  for(int i=0;i<N;i++){
    cin >> K;
    for(int j=0;j<K;j++){
      cin >> tmp;
      A[tmp-1]++;
    }
  }
  for(int h=0;h<M;h++){
    if(A[h]==N){
      res++;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 301;
signed main()
{
#ifdef home
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    int x, y, by;
    cin >> x >> y;
    by = abs(y);
    int ansm = -1, ansp = -1;
    if (x <= -by)
    {
        ansm = -by - x;
        ansp = min(by - x, ansm+1);
    }
    else if (x <= by)
    {
        ansm = by - x + 1;
        ansp = by - x;
        ansm = min(ansm, 1 + by + x + 1);
        ansp = min(ansp, 1 + by + x);
    }
    else
    {
        ansm = 1 + (-by + x);
        ansp = min(1 + (by + x), 1 + ansm);
    }
    if (y < 0)
        cout << ansm;
    else
        cout << ansp;
}

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

int main() {
    int n, ma, mb;
    int dp[410][410];
    cin >> n >> ma >> mb;
    for (int i = 0; i < 410; ++i)
    {
        for (int j = 0; j < 410; ++j)
        {
            dp[i][j] = M;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int j = 409; j >= a; --j)
        {
            for (int k = 409; k >= b; --k)
            {
                dp[j][k] = min(dp[j][k], dp[j - a][k - b] + c);
            }
        }
    }
    int ans = M;
    for (int i = 1; ma * i < 410 && mb * i < 410; ++i)
    {
        ans = min(ans, dp[ma * i][mb * i]);
    }
    if (ans < M)
    {
        cout << ans << "\n";
    }
    else
    {
        cout << "-1\n";
    }
    return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int Min(int a, int b, int c) {
	if (a <= b) { return std::min(a, c); }
	else return std::min(b, c);
}
int main(void) {
	int a, b, x; cin >> x >> a >> b;
	if (abs(a - x) > abs(b - x)) {
		cout << "B" << endl;
	}
	else cout << "A" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

bool F[100][10];
ll P[100][11];
int c[100];

int ret_num(int bin, int f){
    int num = 0;
    REP(i,10){
        bool b = (bin >> i) & 1;
        if(b & F[f][9-i])
            num++;
    }
    return num;
}

int main(){
    int N;
    cin >> N;
    REP(i,N)
        REP(k,10)
            cin >> F[i][k];
    REP(i,N)
        REP(k,11)
            cin >> P[i][k];

    ll max = -1000000000000;
    ll sum;
    for(int b = 1; b < 1024; b++){
        sum = 0;
        REP(i,N)
            c[i] = ret_num(b, i);
        REP(i,N)
            sum += P[i][c[i]];
        //if(b==3) printf("c0=%d, c1=%d, c2=%d, sum=%lld\n",c[0],c[1], c[2],  sum);
        if(sum > max)
            max = sum;
    }
    cout << max << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> pa;

#define fst first
#define snd second
#define pb push_back

const int maxn=300005,maxm=106;
const double pi=acos(-1.0);
const ll mod=1000000007;
const double eps=1e-6;


int b[maxn]={0};
int n,m;
int a[maxn];

int main()
{
	int i,j,k,l;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",a+i);
	ll ans=0;
	for(i=0;i<n;i++)
    {
        if(i-a[i]>0&&i-a[i]<maxn)
        {
            ans+=b[i-a[i]];
        }
        if(i+a[i]<=n) b[i+a[i]]++;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 5384
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	int n,k,x,y;
	cin >> n >> k >> x >> y;
	
	if(n <= k) cout << x*n << endl;
	else cout << x*k + y*(n-k) << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

#define rep(i,n) for(long long i = 0;i<n;i++)
#define REP(i,k,n) for(long long i=k;i<n;i++)

using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int a[200200];
  int x[200200];
  rep(i,n) {
    cin >> x[i];
    a[i] = x[i];
  }
  sort(x,x+n);
  int m = n/2-1;
  rep(i,n){
    if(a[i] <= x[m]){
      cout << x[m+1] << endl;
    }else{
      cout << x[m] << endl;
    }

  }
  return 0;

}


Measured memory_bytes: 3712
def solve(V, G):
    ans = 0
    for i in range(V - 1):
        for j in range(i + 1, V):
            direct = G[i][j]
            for k in range(V):
                if k == i or k == j:
                    continue
                ind = G[i][k] + G[k][j]
                if direct > ind:
                    return -1
                elif direct == ind:
                    break
            else:
                ans += direct
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    print(solve(V, G))


if __name__ == "__main__":
    main()

Measured memory_bytes: 42588
import itertools
n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))

all_on = 0
for sp in itertools.product([0, 1], repeat=n):
    on = 0
    # 電球固定
    for i in range(m):
        cnt = 0
        # スイッチ固定
        for j in range(len(s[i])):
            if sp[s[i][j]-1] == 1:
                cnt += 1
        # 電球iにつながるスイッチのうちON数がpなら対象の電球はON
        if cnt % 2 == p[i]:
            on += 1
    # すべての電球がONなら
    if on == m:
        all_on += 1

print(all_on)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll a, b, x;
    cin>>a>>b>>x;

    cout<<b / x - a / x + (a % x == 0)<<endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}

template<typename T>
T gcd(T x, T y){
    if (x == 0 || y == 0) {
        return 0;
    }

    while (x != y){
        if (x > y) {
            x -= y;
        }else{
            y -= x;
        }
    }
    return x;
}

// }}}
/* vim:set foldmethod=marker: */

void solve(){
    int a1,a2,a3;
    cin >> a1 >> a2 >> a3;

    vi v(3);
    v[0] = abs(a1-a2);
    v[1] = abs(a1-a3);
    v[2] = abs(a3-a2);
    sort(all(v));
    cout << v[0] + v[1] << endl;

    return;
}

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

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


// map の key, value を全て抜き出す。
// for (auto itr = mp.begin(); itr != mp.end(); itr++) {
//     cout << "key" << itr->first << " value" << itr->second << endl;
// }


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

#define ul unsigned long int
#define ull unsigned long long
#define li long long int


int main()
{
  int w,h,x,y,r;
  cin>>w>>h>>x>>y>>r;

  w-=r;
  h-=r;

  if ((x>=r)&&(x<=w)&&(y>=r)&&(y<=h)) cout << "Yes"<<endl;
  else cout <<"No"<<endl;

  return 0;
}



Measured memory_bytes: 3092
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;

int n, sv, tv;
int vx[MaxN + 1], vy[MaxN + 1];

int id[MaxN + 1];

int dist;

inline bool comparator(int u, int v)
{
	if (vx[u] != vx[v])
		return vx[u] < vx[v];
	return vy[u] < vy[v];
}

int link[MaxN + 1];

vector<int> adj[MaxN + 1];

inline void add(int u, int v)
{
	adj[u].push_back(v);
	adj[v].push_back(u);
}

inline bool check(int u, int v, int d)
{
	if (vx[u] != vx[v] + dist)
		return vx[u] < vx[v] + dist;
	return vy[u] < vy[v] + d;
}

inline void build_graph(int d)
{
	sort(id + 1, id + n + 1, comparator);

	int l = 1, r = 1, k = 1;
	for (int i = 1; i <= n; ++i)
	{
		while (l <= n && check(id[l], id[i], -d))
			++l;
		while (r <= n && check(id[r], id[i], d + 1))
			++r;

		link[id[i]] += r - l;

		if ((k = max(k, l)) != r)
		{
			add(id[i], id[k]);
			while (k + 1 < r)
				add(id[k], id[k + 1]), ++k;
		}
	}
}

s64 res = 0;

bool vis[MaxN + 1];

void dfs(int u)
{
	vis[u] = true;

	res += link[u];
	for (int v : adj[u])
		if (!vis[v])
			dfs(v);
}

int main()
{
	cin >> n >> sv >> tv;
	for (int i = 1; i <= n; ++i)
	{
		int x = getint(), y = getint();
		vx[i] = x + y;
		vy[i] = x - y;
	}

	for (int i = 1; i <= n; ++i)
		id[i] = i;

	dist = max(abs(vx[sv] - vx[tv]), abs(vy[sv] - vy[tv]));

	build_graph(dist);

	for (int i = 1; i <= n; ++i)
		swap(vx[i], vy[i]);

	build_graph(dist - 1);

	dfs(sv);

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 13568
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; ++i) cin >> a[i];
  auto b = a;
  sort(b.begin(), b.end());
  assert(a == b);
  int q;
  cin >> q;
  while(q--) {
    int k;
    cin >> k;
    auto it = lower_bound(a.begin(), a.end(), k);
    cout << distance(a.begin(), it) << endl;
  }
  return 0;
}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 300003, M = N << 2;

int n, m;
int tr[N];
struct Node {int l, r, len;} x[N];
int ans[N];

inline int lowbit(int i) {return i & (-i);}

inline void add(int x, int val)
{
	for (int i = x; i <= m; i += lowbit(i)) tr[i] += val;
}

inline int getans(int x)
{
	int sum = 0;
	for (int i = x; i; i -= lowbit(i)) sum += tr[i];
	return sum;
}

inline bool cmp(Node x, Node y) {return x.len < y.len;}

int main()
{
	//File("");
	n = gi <int> (), m = gi <int> ();
	for (int i = 1; i <= n; i+=1)
		x[i].l = gi <int> (), x[i].r = gi <int> (), x[i].len = x[i].r - x[i].l + 1, add(x[i].l, 1), add(x[i].r + 1, -1);
	sort(x + 1, x + 1 + n, cmp);
	int now = n;
	for (int i = m; i >= 1; i-=1)
	{
		while (now >= 1 && x[now].len >= i)
			add(x[now].l, -1), add(x[now].r + 1, 1), --now;
		ans[i] = n - now;
		for (int j = i; j <= m; j+=i) ans[i] += getans(j);
	}
	for (int i = 1; i <= m; i+=1) printf("%d\n", ans[i]);
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<ll, ll> P;

#define rep(a,n) for(int a = 0;a < n;a++)

struct BSearch {
	static ll solve(ll left, ll right, function<ll(ll)> pred) {
		while (right - left > 1) {
			ll middle = left + right;
			middle /= 2;
			if (pred(middle)) {
				right = middle;
			}
			else {
				left = middle;
			}
		}
		return right;
	}
};

int main(void)
{
	ll n, k;
	cin >> n >> k;
	vector<ll> as(n);
	vector<ll> fs(n);
	rep(i, n) cin >> as[i];
	rep(i, n) cin >> fs[i];
	sort(as.begin(), as.end());
	sort(fs.begin(), fs.end(), greater<ll>());
	ll left = -1, right = 2e12 + 10;
	auto r = BSearch::solve(left, right, 
		[&](ll m) {
			ll rest = k;
			rep(i, n) {
				if (rest < 0) return false;
				auto diff = (as[i] * fs[i]) - m;
				if (diff > 0) {
					rest -= (diff % fs[i] == 0) ? diff / fs[i] : diff / fs[i] + 1LL;
				}
			}
			return rest >= 0;
		});
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 3328
use std::io::*;
use std::str::*;

// const MOD: i32 = 1000000007;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: usize = read().unwrap();

    // 0 initialize
    let mut a: [u32; 100001] = [0; 100001];

    for _ in 0..n {
        let tmp: usize = read().unwrap();
        a[tmp] += 1;
    }


    let mut ans = 0;
    for i in 1..100000 {
        let cnt = a[i - 1] + a[i] + a[i + 1];
        ans = std::cmp::max(cnt, ans);
    }
    ans = std::cmp::max(ans, a[0] + a[1]);
    ans = std::cmp::max(ans, a[100000] + a[99999]);
    println!("{}", ans);

}


Measured memory_bytes: 4732
#include <stdio.h>
#include <stdint.h>

int main(void)
{
  int64_t N, A, B;
  scanf("%ld %ld %ld", &N, &A, &B);
  
  int64_t ans;
  ans = N / (A + B) * A;
  
  if(N % (A + B) > A)
    ans += A;
  else
    ans += (N % (A + B));
  
  printf("%ld", ans);
  
  return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
struct line{
    int l,r;  
}p[200005];
bool cmp1(line a,line b){
    return a.l<b.l;
    
}
bool cmp2(line a,line b){
    return a.r<b.r;
    
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].l>>p[i].r;
    }
    if(n%2==0){
        int ans1=0,ans2=0;
        sort(p+1,p+n+1,cmp1);
        ans1=p[n/2].l+p[n/2+1].l;
        sort(p+1,p+n+1,cmp2);
        ans2=p[n/2].r+p[n/2+1].r;
        cout<<ans2-ans1+1; 
    }
    else {
        int ans1=0,ans2=0;
        sort(p+1,p+n+1,cmp1);
        ans1=p[n/2+1].l;
        sort(p+1,p+n+1,cmp2);
        ans2=p[n/2+1].r;
        cout<<ans2-ans1+1; 
    }
    cout<<endl;
}


Measured memory_bytes: 5132
s = input()
s_len = len(s)
t = input()
t_len = len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]
for i in range(s_len):
    S = s[i]
    for j in range(t_len):
        T = t[j]
        ni = i + 1
        nj = j + 1
        if S == T:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1, dp[i][nj], dp[ni][j])
        else:
            dp[ni][nj] = max(dp[ni][nj], dp[i][nj], dp[ni][j])

nagasa = dp[s_len][t_len]

a = s_len
b = t_len
ans = []
while nagasa > 0:
    if dp[a][b] == nagasa:
        a -= 1
    elif dp[a + 1][b] == nagasa:
        b -= 1
    else:
        ans.append(s[a])
        nagasa -= 1
ans = ans[::-1]
print(*ans, sep="")


Measured memory_bytes: 114652
#include <iostream>
#include <vector>

using namespace std;
bool recursive(int N, int K, vector<int>& a, bool turn,
               vector<vector<int>>& table) {
  if (table[K][turn] != -1) return table[K][turn];
  if (K < a[0]) {
    table[K][turn] = !turn;
    return !turn;
  } else {
    for (int i = 0; i < N; ++i) {
      if (K - a[i] < 0) break;
      bool result = recursive(N, K - a[i], a, !turn, table);
      if (result == turn) {
        table[K][turn] = turn;
        return turn;
      }
    }
    table[K][turn] = !turn;
    return !turn;
  }
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N, 0);
  for (int i = 0; i < N; ++i) cin >> a[i];
  vector<vector<int>> table(K + 1, vector<int>(2, -1));
  bool result = recursive(N, K, a, false, table);
  if (result)
    cout << "Second";
  else
    cout << "First";
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,p,q,c[500005];
priority_queue<pair<ll,int> >que;
struct BIT
{
	int bit[(1<<20)+5];
	int f(int x)
	{
		return x&-x;
	}
	void add(int i,int x)
	{
		for(int s=i;s<=(1<<20);s+=f(s)) bit[s]+=x;
	}
	int sum(int i)
	{
		int res=0;
		for(int s=i;s>0;s-=f(s)) res+=bit[s];
		return res;
	}
}bit;
int main(){
	scanf("%d%d%d",&n,&p,&q);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=n;i++){
		que.push(mp(1LL*i*p+c[i],i));
	}
	ll ret = 0,cur,Q = q;
	for(int i=1;i<=n;i++){
		ret += 1LL*Q*p; Q++;
	}
	cur = ret;
	int cnt = 0;
	while(!que.empty()){
		int id = que.top().sc; que.pop();
		cur += c[id];
		cur -= 1LL*(q+id-1-2*bit.sum(id-1))*p;
		cur -= (n-id-cnt+bit.sum(id-1))*2*p;
		ret = max(ret,cur);
		bit.add(id,1); cnt++;
	}
	cout << ret << endl;
}

Measured memory_bytes: 14944
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

ll BallBoxCombination11(ll n,ll k){
	return (n>k) ? 0 : 1;
}

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

	ll N=in<ll>(),K=in<ll>();
	
	ll ans = BallBoxCombination11(N,K);
	out(ans);
	return 0;
}



Measured memory_bytes: 3084
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;

ll dp[55][55][2505];

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,a;
    cin>>n>>a;
    V<ll> x(n);
    cinf(n,x);
    dp[0][0][0]=1;
    rep(i,n){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n*a;k++){
                dp[i+1][j][k]+=dp[i][j][k];
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k];
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=dp[n][i][i*a];
    out(ans);
}

Measured memory_bytes: 54584
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int count = 0;
  for(int i=0;i<n;i+=1){
    int d1,d2;
    cin >> d1 >> d2;
    if(d1 == d2){
      count+=1;
      if(count == 3) break;
    }else{
      count = 0;
    }
  }
  
  if(count == 3) cout << "Yes";
  else cout << "No";
  
  return 0;
}

Measured memory_bytes: 3672
#12:26
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
same = []
b = []
for i in range(1,n):
  if a[i-1] == a[i]:
    same.append(a[i])
    ans += 1
    a[i-1] = 0
    a[i] = 0
for i in range(n):
  if a[i] != 0:
    b.append(a[i])
#print(same,ans,b)
p = [0 for _ in range(k)]
q = [0 for _ in range(k)]
r = [0 for _ in range(k)]
for x in same:
  p[x%k] += 2
for x in b:
  q[-(x%k)] += 1
  r[x%k] += 1
#print(p)
#print(q)
#print(r)
#print(ans)
for i in range(k):
  if i*2 % k == 0:
    mini = min(q[i],r[i]) // 2
  else:
    mini = min(q[i],r[i])
  q[i] -= mini
  r[i] -= mini
  q[-i] -= mini
  r[-i] -= mini
  ans += mini
#print(p)
#print(q)
#print(r)
#print(ans)
for i in range(k):
  mini = min(p[i],q[i]) // 2
  if mini > 0:
    ans += mini
print(ans)

Measured memory_bytes: 14008
#include<iostream>

using namespace std;

int H, W;
bool in[50][50];

int vx[8] = { -1,0,1,1,1,0,-1,-1 };
int vy[8] = { -1,-1,-1,0,1,1,1,0 };

int retVal(int a, int b) {
	int rev = 0;
	for (int i = 0; i < 8; i++) {
		int nx = a + vx[i], ny = b + vy[i];
		if (nx < 0 || nx >= H || ny < 0 || ny >= W)continue;
		if (in[nx][ny])rev++;
	}
	return rev;
}

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char c;
			cin >> c;
			if (c == '#')in[i][j] = true;
			else in[i][j] = false;
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (in[i][j])cout << "#";
			else cout << retVal(i, j);
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
while 1:
    nums=[i for i in range(1,502)]
    l,r=0,2
    n=int(input())
    if(n==0):
        break
    ans=0
    while r<len(nums):
        if r-l<2:
            r+=1
            continue
        if sum(nums[l:r])==n:
            ans+=1
            l+=1
        elif sum(nums[l:r])>n:
            l+=1
        else:
            r+=1
    print(ans)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)

int N;
int a[20];

int main(){

    cin >> N;
    if(N==3 || N==5 || N==7) cout << "YES" << endl;
    else cout << "NO" << endl;


    
    
    return 0;
}


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

string divide[4] = {"dream", "dreamer", "erase", "eraser"};

int main(){
  string S;
  cin >> S;
  
  reverse(S.begin(), S.end());
  for (int i=0; i<4; ++i)reverse(divide[i].begin(), divide[i].end());
  
  bool can_divide = true;
  for(int i=0; i<S.size();){
    bool has_same_string = false;
    for (int j=0; j<4; ++j){
      string temp_word = divide[j];
      if (S.substr(i, temp_word.size()) == temp_word){
        has_same_string = true;
        i += temp_word.size();
      }
    }
    if (!has_same_string){
      can_divide = false;
      break;
    }
  }
  
  if(can_divide) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

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

int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> H(N);
    for(int i=0;i<N;i++) cin >> H[i];

    vector<vector<int>> path(N);

    for(int i=0;i<M;i++)
    {
        int a,b;
        cin >> a >> b;
        path[a-1].push_back(b-1);
        path[b-1].push_back(a-1);
    }

    int cnt=0;
    for(int i=0;i<N;i++)
    {
        bool isGood = true;
        ll rootHeight = H[i];
        for(auto j:path[i])
        {
            if(rootHeight <= H[j])
            {
                isGood = false;
            }
        }
        if(isGood) cnt++;
    }

    cout << cnt;

    return 0;
}


Measured memory_bytes: 9072
#include <iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1 << 21);
static const int NOT_VISIT = 0;
static const int VISITING = 1;
static const int VISITED = 2;
int n;
int M[MAX][MAX];
int prim()
{
    int minv, u;
    int isVisited[MAX], d[MAX], p[MAX];
    for (int i = 0; i < n; i++) {
	isVisited[i] = NOT_VISIT;
	d[i] = INFTY;
	p[i] = -1;
    }
    d[0] = 0;
    while (1) {
	minv = INFTY;
	u = -1;
	for (int i = 0; i < n; i++) {
	    if (minv > d[i] && isVisited[i] != VISITED) {
		u = i;
		minv = d[i];
	    }
	}
	if (u == -1) {
	    break;
	}

	isVisited[u] = VISITED;
	for (int j = 0; j < n; j++) {
	    if (isVisited[j] != VISITED && M[u][j] != INFTY) {
		if (d[j] > M[u][j]) {
		    d[j] = M[u][j];
		    p[j] = u;
		    isVisited[j] = VISITING;
		}
	    }
	}
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
	if (p[i] != -1) {
	    sum += M[i][p[i]];
	}
    }
    return sum;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	    int e;
	    cin >> e;
	    M[i][j] = (e == -1) ? INFTY : e;
	}
    }
    cout << prim() << endl;
}

Measured memory_bytes: 3084
#include <stdio.h>

int main(void) {
  int n,i,a,max=-1000000,min=1000000;
  long int sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    if(max<a){
      max=a;
    }
    if(min>a){
      min=a;
    }
    sum+=a;
    }
 
  printf("%d %d %ld\n",min,max,sum);

  return 0;
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;
 
double eps=1e-8;
 
bool eq(double a,double b){
  return (-eps<a-b&&a-b<eps);
}
 
bool eq(P a,P b){
  return (abs(a-b)<eps);
}
 
double dot(P a,P b){
  return real(b*conj(a));
}
 
double cross(P a,P b){
  return imag(b*conj(a));
}
     
bool isParallel(P a,P b){
  return eq( cross(a,b) , 0 );
}
 
 
struct S{
  P p,q;
  S(P a=P(0,0),P b=P(0,0)):p(a),q(b){}
  P base(){    return q-p;  }
};
 
typedef S L;
 
double getDistanceLP(L l,P p){
  P a=l.p,b=l.q;
  return abs( cross(b-a,p-a) ) / abs(b-a);
}
 
double getDistanceSP(S s,P p){
  P a=s.p;
  P b=s.q;
  if( dot(b-a,p-a) < eps )return abs(p-a);
  if( dot(a-b,p-b) < eps )return abs(p-b);
  return getDistanceLP(s,p);
}
 
P reflect(S s,P p){
  P a=s.p;
  P b=s.q;
  p-=a;
  b-=a;
  return a+conj(p/b)*b;
}
 
bool onLine(L l,P p){
  P a=l.p;
  P b=l.q;
  return eq(0, cross(p-a,b-a) );
}
 
bool onSegment(S s,P p){
  P a=s.p;
  P b=s.q;
  return eq( abs(a-b) , abs(p-a) + abs(p-b) );
}
 
P getCrossPoint(S s1,S s2){
  P a=s1.p, b=s1.q;
  P c=s2.p, d=s2.q;
  a-=d,b-=d,c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}
 
bool isIntersectLS(L li,S se){
  P a=li.p;
  P b=li.q;
  double A=cross(b-a,se.p-a);
  double B=cross(b-a,se.q-a);
  return (A*B<eps);
}
 
P input(){
  double x,y;
  cin>>x>>y;
  return P(x,y);
}
 
int N;
S t[5];
P si,ti;
int tl[10];
double ans;
 
double calc(P p,P v,int depth){
 
  if( eq(p,ti) ) return 0;
   
  P np,nv;
   
  if(depth>6)return 1e20;
   
  double mini=1e20;
  for(int i=0;i<N;i++){
    S seg=t[i];
    if(onSegment(seg,p))continue;
    L li=L(p,p+v);
    if( !isIntersectLS(li,seg) )continue;
    P k=getCrossPoint( li, seg );
    assert( onSegment(seg,k) );
    assert( onLine(li,k) );
    if( dot(k-p,v) < 0 )continue;
    if(mini>abs(k-p)){
      mini=abs(k-p);
      np=k;
      nv=reflect(seg,k+v)-k;
    }
  }
 
  if( isParallel(v,ti-p) && dot(v,ti-p) > 0 ){
    if( mini > abs(ti-p)){
      return abs(ti-p);
    }
  }
 
  if(mini==1e20)return 1e20;
  return mini+calc(np,nv,depth+1);
}
 
P ansve;
void check(int size,P target){
  P v=target-si;
  if( abs(v) < eps )return;
  double dist=calc(si,v,0);
  if(ans>dist){
    ans=dist;
    ansve=v;
  }
}
 
void dfs(int depth, P target){
  check(depth,target);
  if(depth==6)return;
  for(int i=0;i<N;i++){
    dfs(depth+1, reflect(t[i],target) );
  }
}
 
int main(){
  while(1){
    cin>>N;
    if(N==0)break;
    for(int i=0;i<N;i++){
      P a=input();
      P b=input();
      t[i]=S(a,b);
    }
    ti=input();
    si=input();
    ans=1e20;
    dfs(0,ti);
    printf("%.10f\n",ans);
  }
  return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  int sum = A + B;
  if(sum == 3){
    cout << "3" << endl;
  }else if(sum == 4){
    cout << "2" << endl;
  }else if(sum == 5){
    cout << "1" << endl;
  }
  return 0;
}

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

template<class INT>
std::vector<INT> factorize(INT n){
    std::vector<INT> res;
    for (INT i = 1; i * i <= n; i++){
        if (n % i == 0){
            res.push_back(i);
            if (i * i != n)
                res.push_back(n / i);
        }
    }
    return res;
}

int main(){
    int64_t n;
    cin >> n;
    int64_t ans = n;
    auto res = factorize(n);
    for (const auto &r: res)
        ans = min(ans, r - 1 + n / r - 1);

    cout << ans << endl;
}

Measured memory_bytes: 384
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
k = ini()
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        d = gcd(a,b)
        for c in range(1,k+1):
            ans += gcd(d,c)
print(ans)

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

using ll = long long;
#define countof(a) (sizeof(a)/sizeof((a)[0]))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 

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

    int H,W; cin >>H>>W;
    string S;
    
    rep(i, H) {
        rep(j, W) {
            cin >> S;
            if (S == "snuke") {
                cout << char('A' + j) << i + 1 << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,x=0;
int32_t main(){
CODE_START;
cin>>n;
ll x=n/500;
ll ans=ans+x*1000;
n=n-x*500;
x=n/5;
n=n-n%5;
ans=ans+n;
cout<<ans<<endl;
}


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

#define ll          long long
#define endl        "\n"
#define infL        LLONG_MAX
#define infI        INT_MAX
#define pb          push_back
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define MAX         100
#define yes         cout<<"YES"<<endl
#define no          cout<<"NO"<<endl
#define bye         return 0
#define PEREGRINE_FALCON {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}

ll mod=1e9+7;

int main()
{
      PEREGRINE_FALCON
      //freopen("inputNew.txt", "r", stdin);

      ll tt=1;
      while(tt--){
            ll n,mn,mx,temp,cnt;
            cin>>n;
            ll a[n],b[n];
            for(int i=0; i<n; i++){
                  cin>>a[i]>>b[i];
            }

            bool found=false;
            mx=0;
            cnt=0;
            for(int i=0; i<n; i++){
                  if(a[i]==b[i]) {cnt++;continue;}
                  mx=max(mx,cnt);
                  cnt=0;
            }
            mx=max(mx,cnt);
            if(mx>=3){cout<<"Yes"<<endl;}
            else cout<<"No"<<endl;
      }


      bye;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}
int main(){
    ll n,t;
    cin >> n >> t;
    vector<ll>x(n);
    ll ans=0;
    rep(i,n) cin >> x[i];
    rep(i,n-1){
        ans+=min(t,x[i+1]-x[i]);
    }
    ans+=t;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
import queue

WHITE = 0
GRAY = 1
BLACK = 2

NIL = -1
INF = 1000000000


def bfs(u):
    global Q
    Q.put(u)
    for i in range(n):
        d[i] = NIL
    d[u] = 0
    while not Q.empty():
        u = Q.get()
        for v in range(n):
            if (m[u][v] == 1) and (d[v] == NIL):
                d[v] = d[u] + 1
                Q.put(v)
n = int(input())

m = [[0 for i in range(n + 1)] for j in range(n + 1)]
vid = [0] * n
d = [0] * n
f = [0] * n
Q = queue.Queue()
color = [WHITE] * n
time = 0
nt = [0] * n

tmp = []
for i in range(n):
    nums=list(map(int,input().split()))
    tmp.append(nums)
    vid[i] = nums[0]

for i in range(n):
    for j in range(tmp[i][1]):
        m[i][vid.index(tmp[i][j + 2])] = 1

bfs(0)

for i in range(n):
    print(vid[i], d[i])






Measured memory_bytes: 6944
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

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

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)

typedef long long LL;
typedef long double LD;

bool compare_by_a(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first) {
        return a.first < b.first;
    } else {
        return a.second < a.second;
    }
}

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    int A, P;
    cin >> A >> P;

    int ans = 0;
    ans += 3*A;
    ans += P;
    ans /= 2;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, lim = MI()
    ww = []
    vv = []
    for _ in range(n):
        w, v = MI()
        ww.append(w)
        vv.append(v)
    w0=ww[0]
    # dp[i][j]…荷物の個数がiで、端数の合計がjのときの価値の最大値
    dp=[[0]*(3*n+1) for _ in range(n+1)]
    for w,v in zip(ww,vv):
        for i in range(n,0,-1):
            sj=min(lim-i*w0,3*n)
            for j in range(sj,-1,-1):
                nj=j-(w-w0)
                if nj<0:break
                dp[i][j]=max(dp[i][j],dp[i-1][nj]+v)
    #p2D(dp)
    print(max(max(row) for row in dp))

main()


Measured memory_bytes: 4212
N, M = (int(i) for i in input().split())

x = []
y = []
z = []
for i in range(N):
    data = [int(i) for i in input().split()]
    x.append(data[0])
    y.append(data[1])
    z.append(data[2])

def get_max_cakes(x_rev, y_rev, z_rev):
    if x_rev:
        X = [-i for i in x]
    else:
        X = x

    if y_rev:
        Y = [-i for i in y]
    else:
        Y = y

    if z_rev:
        Z = [-i for i in z]
    else:
        Z = z

    cakes = [X[i]+Y[i]+Z[i] for i in range(N)]

    sorted_cakes = sorted(cakes, reverse=True)

    return sum(sorted_cakes[0:M])


max_score = 0

for x_reverse in (False, True):
    for y_reverse in (False, True):
        for z_reverse in (False, True):
            temp = get_max_cakes(x_reverse, y_reverse, z_reverse)
            if temp > max_score:
                max_score = temp

print(max_score)

Measured memory_bytes: 3316
#include <stdio.h>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define NUM (200000)
int pt[NUM];
int sum[12000];

int main() {
    vector<int> ps;
    for (int i = 2; i < NUM; i++) if (pt[i] == 0) {
        ps.push_back(i);
        for (int j = i+i; j < NUM; j+=i) pt[j] = i;
    }
    rep (i, 10000) sum[i+1] = sum[i] + ps[i];
    for (;;) {
        int n;
        scanf("%d", &n);
        if (n == 0) return 0;
        printf("%d\n", sum[n]);
    }
}

Measured memory_bytes: 0
def BFS_one_search(map_,counts,y,x,wall):
    can_be_new_count = []
    new_ques = []
    for i in range(-1,2):
        for j in range(-1,2):
            if i * j == 0 and i != j:
                if counts[y + i][x + j] != -1:
                    can_be_new_count.append(counts[y + i][x + j] + 1)
                elif not(map_[y + i][x + j] in wall):
                    new_ques.append((y + i,x + j))
    new_count = min(can_be_new_count) if len(can_be_new_count) > 0 else 0
    return new_count,new_ques

def breadth_first_search(map_,s_y,s_x,wall = ['#']):
    ques = [(s_y,s_x)]
    counts = []
    for _ in range(len(map_)):
        counts.append([-1] * len(map_[0]))
    while(len(ques) > 0):
        here_count,new_que = BFS_one_search(map_,counts,ques[0][0],ques[0][1],wall)
        counts[ques[0][0]][ques[0][1]] = here_count
        for i in range(len(new_que)):
            if not new_que[i] in ques:
                ques.append(new_que[i])
        ques.pop(0)
    return counts

def make_map_data(H,W,wall = '#',make_wall = True):
    map_ = []
    if make_wall:
        map_.append([wall] * (W + 2))
        for _ in range(H):
            map_.append([wall] + list(input()) + [wall])
        map_.append([wall] * (W + 2))
    else:
        for _ in range(H):
            map_.append(list(input()))
    return map_
H,W= (int(i) for i in input().split())  
s_y = 1
s_x = 1
g_y = H 
g_x = W
map_ = make_map_data(H,W,make_wall = True)
min_counts = breadth_first_search(map_,s_y,s_x)[g_y][g_x]
if min_counts == -1:
    print(-1)
else:
    wall_count = 0
    for y in range(H + 2):
        for x in range(W + 2):
            if map_[y][x] == '#':
                wall_count += 1
    #print(min_counts)
    print((H + 2) * (W + 2) - wall_count - (min_counts + 1))

Measured memory_bytes: 44636
#include <iostream>
#define tri(x) (x * x * x)

using namespace std;

long long N, K;

int main()
{
    cin >> N >> K;

    long long modk = N / K, modk_2 = 0;

    for(int i = K / 2; i <= N; i += K)
        modk_2++;
    
    if(K % 2)
        cout << tri(modk) << '\n';
    else
        cout << tri(modk) + tri(modk_2) << '\n';

    return 0;

}





Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int n[4];
	int ans = 1;
	for (int i = 0; i < 4; ++i)
	{
		scanf("%d",&n[i]);
		if(n[i]!=1&&n[i]!=9&&n[i]!=7&&n[i]!=4){
			ans = 0;
		}
	}
	for (int i = 0; i < 4; ++i)
	{
		for (int j = 0; j < 4; ++j)
		{
			if(i!=j&&n[i]==n[j]){
				ans=0;
			}
		}
	}
	if(ans==1){
		printf("YES");
	}else{
		printf("NO");
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


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


Measured memory_bytes: 256
import math
import collections

n = int(input())
a = list(map(int, input().split()))
num_list = []
ans_total = 0

c = collections.Counter(a)

for d in c:
    if not c[d] == 1:
        ans_total += int(math.factorial(c[d])/(2*math.factorial(c[d]-2)))

for i in range(n):
    print(ans_total-c[a[i]]+1)

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

using namespace std;

#define PB push_back
#define MP make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define RFOR(i, b, a) for (int i = b-1; i>=a; --i)
#define FILL(a, b) memset(a, b, sizeof a)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef pair<LL, LL> PLL;

const int INF = 1000 * 1000 * 1000;
const LL LINF = 1LL * INF*INF;
const int MAX = 100010;
const long double PI = acos(-1.);
const double EPS = 1e-6;
LL mod = 1000LL*1000*1000 + 7;

VI g[105];

int main()
{
	ios_base::sync_with_stdio(0); double startClock = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	if(n%2)
	{
		g[0].PB(n);
		FOR(i,1,n/2 + 1)
		{
			g[i].PB(i);
			g[i].PB(n-i);
		}
		vector<PII> ans;
		FOR(i,0,n/2+1)
		{
			FOR(j,i+1,n/2+1)
			{
				for(auto v1:g[i])
				{
					for(auto v2:g[j])
					{
						ans.PB(MP(v1,v2));
					}
				}
			}
		}
		cout << SZ(ans) << endl;
		FOR(i,0,SZ(ans))
			cout << ans[i].f << " " << ans[i].s << endl;
	}
	else
	{
		FOR(i,1,n/2 + 1)
		{
			g[i].PB(i);
			g[i].PB(n+1-i);
		}
		vector<PII> ans;
		FOR(i,1,n/2+1)
		{
			FOR(j,i+1,n/2+1)
			{
				for(auto v1:g[i])
				{
					for(auto v2:g[j])
					{
						ans.PB(MP(v1,v2));
					}
				}
			}
		}
		cout << SZ(ans) << endl;
		FOR(i,0,SZ(ans))
			cout << ans[i].f << " " << ans[i].s << endl;
	}











	cerr << endl << (clock() - startClock)/CLOCKS_PER_SEC << endl;return 0;
}


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

int main(){
	int n;
	cin >> n;
	
	vector<int>v(n);
	for(int i = 0; i < n; i++)
		cin >> v[i];
	
	int ans = 1, tmp = 0, a = v[0];
	
	for(int i = 0; i < n; i++){
		if(a == 2) break;
		tmp = a - 1;
		a = v[tmp];
		
		ans++;
		
		
		if(i == n - 1) ans = -1;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 640
#include<cstdio>
using namespace std;
int main(){
 int w,h;
 int cnt=0;
 while(1){
  scanf("%d %d",&h,&w);
  if(w==0 && h==0){ 
   return 0;
  }
  for(int i=0;i<h;i++){
   for(int j=0;j<w;j++){
    if((i+j)%2==0){
     printf("#");
    }else{
     printf(".");
    }
   }
   printf("\n");
  }
  printf("\n");
 }
}


Measured memory_bytes: 2604
from collections import deque

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

res = deque()
for i in range(0, N-1, 2):
    res.append(A[i])
    res.appendleft(A[i+1])

if N % 2 == 1:
    res.append(A[N-1])
    print(" ".join(reversed([str(s) for s in res])))
else:
    print(" ".join(str(s) for s in res))

Measured memory_bytes: 37872
import java.util.Scanner;

public class Main {

	static char[][] A;
	static final int[] dx = { 1, 0 };
	static final int[] dy = { 0, 1 };
	static int H;
	static int W;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		H = in.nextInt();
		W = in.nextInt();
		A = new char[H][W];
		int countS = 0;
		for (int i = 0; i < H; i++) {
			A[i] = in.next().toCharArray();
			for (int j = 0; j < A[i].length; j++) {
				if (A[i][j] == '#') {
					countS++;
				}
			}
		}
		boolean[][] seen = new boolean[H][W];
		dfs(0, 0, seen);
		int count = 0;
		for (int i = 0; i < seen.length; i++) {
			for (int j = 0; j < seen[i].length; j++) {
				if (seen[i][j] == true) {
					count++;
				}
			}
		}
		System.out.println(countS == count ? "Possible" : "Impossible");
		in.close();
	}

	static void dfs(int h, int w, boolean[][] seen) {
		seen[h][w] = true;
		if (w - 1 >= 0 && seen[h][w - 1] == false && A[h][w - 1] == '#') {
			return;
		}
		if (h - 1 >= 0 && seen[h - 1][w] == false && A[h - 1][w] == '#') {
			return;
		}
		if ((h + 1 < H && A[h + 1][w] == '#') && (w + 1 < W && A[h][w + 1] == '#')) {
			return;
		}
		for (int i = 0; i < 2; i++) {
			int nh = h + dx[i];
			int nw = w + dy[i];
			if (nh >= H || nw >= W)
				continue;
			if (A[nh][nw] == '.')
				continue;
			if (seen[nh][nw] == true)
				continue;
			// 再帰的に探索
			dfs(nh, nw, seen);
		}
	}
}

Measured memory_bytes: 23892
import datetime

h1, m1, h2, m2, k = map(int,input().split())

dt1 = h1 * 60 + m1

dt2 = h2 * 60 + m2

#dt1 = datetime.timedelta(hours = h1, minutes=m1)
#dt2 = datetime.timedelta(hours = h2, minutes=m2)

#m = datetime.timedelta(minutes=k)

dt3 = dt2 - k

dt4 = dt3 - dt1

print(dt4)

Measured memory_bytes: 9328