Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 震惊！

Posted by 1843172768 at 2020-01-12 15:43:10 on Problem 1276
```别走！

//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i<(b);i++)
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define pb push_back
#define fi first
#define se second
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%I64d", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
void W(){}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
void _R(const int& x){ scanf("%d", &x); }
void _R(const ll& x){ scanf("%I64d", &x); }
void _R(const char* x){ scanf("%s", x); }
void R(){}
const ll mod = 1e9+7;
ll ft1(ll a,ll b){ll ans = 1;while (b){if (b&1) ans *= a;b>>=1,a*=a;}return ans;}
ll ft2(ll a,ll b){ll ans = 1;while (b){if (b&1) ans = ans*a%mod;b>>=1,a=a*a%mod;}return ans;}

const int N = 1e5+5;

int l[N],r[N];

int dp[2][N];
int v[N],w[N],n[N];

struct P{
int fi,se;
}sta[N];

int main()
{
int V,m;

while (~scanf("%d %d",&V,&m)){

memset(dp[0],0,sizeof(int)*(V+1));
memset(dp[1],0,sizeof(int)*(V+1));

for1(i,1,m) R(n[i],w[i]),v[i] = w[i];

int cur = 0,now = 1;

for1(i,1,m){//前i件
for0(d,0,v[i]){//余数为d

int st=1,ed=0;
for (int x=0;x*v[i]<=V;x++){//求dp[i][d+x*v] = sta[max(x-n[i]+1,0)~x] + x*w[i]
int ww = dp[cur][d+x*v[i]] - x*w[i];
while (st<=ed && ww>sta[ed].se) ed--;
sta[++ed] = {x,ww};
int border = max(x-n[i],0);
while (st<=ed && sta[st].fi<border) st++;
dp[now][d+x*v[i]] = sta[st].se + x*w[i];
}
}
swap(cur,now);
}
W(dp[cur][V]);

}
return 0;
}```

Followed by: