2019-10-14 11:02:08

$$\frac{t(t+1)}{2}<w$$

$$t=\left\lfloor\sqrt{2x+\frac{1}{4}}-\frac{1}{2}\right\rfloor$$

\begin{aligned}&\sum_{i=0}^t\left(w-\sum_{j=0}^ij\right)\\=&(t+1)w-\sum_{i=0}^t\frac{i(i+1)}{2}\\=&(t+1)w-\left(\frac{t(t+1)(2t+1)}{12}+\frac{t(t+1)}{4}\right)\\=&(t+1)w-\frac{t(t+1)(t+2)}{6}\end{aligned}

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}

const int N=1000000+10;

int n,m;

struct sedge { int u,v,w; } se[N];

struct edge { int v,w,nxt; } e[N];
inline void addEdge(int u,int v,int w) {
}

int dfn[N],low[N],tim=0,sta[N],in[N],top=0,bl[N],tot=0;
inline void tarjan(int u) {
dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
int v=e[i].v;
if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if (in[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u]) { ++tot;
while (233) {
int t=sta[top--]; in[t]=0,bl[t]=tot;
if (u==t) break;
}
}
}

int w[N],dp[N];
inline int dfs(int u) {
if (dp[u]) return dp[u];
dp[u]=max(dp[u],e[i].w+dfs(e[i].v));
return dp[u]+=w[u];
}

inline int calc(int w) {
int t=sqrt(2*w+0.25)-0.5;
return w*(t+1)-(t+1)*(t+2)*t/6;
}

signed main() {
for (re int i=1;i<=m;++i) {
}